A compressed sensing method consists of a rectangular measurement matrix, @math with @math , together with an associated recovery algorithm, @math . Compressed sensing methods aim to construct a high quality approximation to any given input vector @math using only @math as input. In particular, we focus herein on instance optimal nonlinear approximation error bounds for @math and @math of the form @math for @math , where @math is the best possible @math -term approximation to @math . In this paper we develop a compressed sensing method whose associated recovery algorithm, @math , runs in @math -time, matching a lower bound up to a @math factor. This runtime is obtained by using a new class of sparse binary compressed sensing matrices of near optimal size in combination with sublinear-time recovery techniques motivated by sketching algorithms for high-volume data streams. The new class of matrices is constructed by randomly subsampling rows from well-chosen incoherent matrix constructions which already have a sub-linear number of rows. As a consequence, fewer random bits than previously required are needed in order to select the rows utilized by the fast reconstruction algorithms considered herein.
Perhaps the measurement matrices considered herein are most similar to previous compressed sensing matrices based on unbalanced expander graphs (see, e.g., @cite_20 @cite_23 @cite_9 ). Indeed, the measurement matrices used in this paper are created by randomly sampling rows from larger binary matrices that are, in fact, the adjacency matrices of a subclass of unbalanced expander graphs. However, unlike previous approaches which use the properties of general unbalanced expanders, we use different combinatorial techniques which allow us to develop @math -time recovery algorithms. To the best of our knowledge, the runtimes we obtain by doing so are the best known for any such method having @math '' error guarantees.
@cite_9 @cite_23 @cite_20
2140466267 2130979540
Expander graphs have been recently proposed to construct efficient compressed sensing algorithms. In particular, it has been shown that any n-dimensional vector that is k-sparse can be fully recovered using O(klogn) measurements and only O(klogn) simple recovery iterations. In this paper, we improve upon this result by considering expander graphs with expansion coefficient beyond 3 4 and show that, with the same number of measurements, only O(k) recovery iterations are required, which is a significant improvement when n is large. In fact, full recovery can be accomplished by at most 2k very simple iterations. The number of iterations can be reduced arbitrarily close to k, and the recovery algorithm can be implemented very efficiently using a simple priority queue with total recovery time O(nlog(n k))). We also show that by tolerating a small penalty on the number of measurements, and not on the number of recovery iterations, one can use the efficient construction of a family of expander graphs to come up with explicit measurement matrices for this method. We compare our result with other recently developed expander-graph-based methods and argue that it compares favorably both in terms of the number of required measurements and in terms of the time complexity and the simplicity of recovery. Finally, we will show how our analysis extends to give a robust algorithm that finds the position and sign of the k significant elements of an almost k-sparse signal and then, using very simple optimization techniques, finds a k-sparse signal which is close to the best k-term approximation of the original signal. We consider the approximate sparse recovery problem, where the goal is to (approximately) recover a high-dimensional vector xisinRopfn from its lower-dimensional sketch AxisinRopfm. Specifically, we focus on the sparse recovery problem in the L1 norm: for a parameter k, given the sketch Ax, compute an approximation xcirc of x such that the L1 approximation error parx-xcircpar1 is close to minx' parx-x'par1, where x' ranges over all vectors with at most k terms. The sparse recovery problem has been subject to extensive research over the last few years. Many solutions to this problem have been discovered, achieving different trade-offs between various attributes, such as the sketch length, encoding and recovery times. In this paper we provide a sparse recovery scheme which achieves close to optimal performance on virtually all attributes (see Figure 1). In particular, this is the first recovery scheme that guarantees O(k log(n k)) sketch length, and near-linear O(n log (n k)) recovery time simultaneously. It also features low encoding and update times, and is noise-resilient.