2013 · 13 citations · 29 references
ComputingComputer ScienceElectrical EngineeringComputer NetworksPropagationTopologyNetwork AnalysisNetwork ConnectivityNetwork InferenceNetwork RecoveryNetwork StructureNetwork TopologyCompressed SensingCompressive SensingNetwork ConstraintsNetwork Topology ReconstructionSparse Network EstimationSparse ReconstructionTomographyTopological Constraints
This paper addresses the problem of recovering sparse link vectors with network topological constraints that is motivated by network inference and tomography applications. We propose a novel framework called UCS-NT in the context of compressive sensing for sparse recovery in networks. In order to efficiently recover sparse specification of link vectors, we construct a feasible measurement matrix using this framework through connected paths. It is theoretically shown that, only O(k log(n)) path measurements are sufficient for uniquely recovering any k-sparse link vector. Moreover, extensive simulations demonstrate that this framework would converge to an accurate solution for a wide class of networks.
29
David L. Donoho · IEEE Transactions on Information Theory · 2006 · 23.1K citations
Monte Carlo sampling methods using Markov chains and their applications
W. Keith Hastings · Biometrika · 1970 · 15.2K citations