ALGORITHMIC EMBEDDINGS

Compressible signals are pervasive in signal processing applications. The essential feature of a compressible signal is that it can be approximated well by a sparse signal. It has recently been observed that it is possible to collect the essential information from a compressible signal by projecting it onto a low-dimensional random subspace. This idea is called sketching in computer science and compressed sensing in signal processing.

The geometric functional analysis has studied non-algorithmic aspects of projections onto random low-dimensional subspaces since 1980s. Many tools are now available to check if such a projection is an almost isometry on a class of functions (a set of vectors in R^d). None of these, however, suggest reconstruction algorithms. Suppose we know that a certain projection is an almost isometry on a certain set in R^d. Is it possible to reconstruct points in the set from their projections in polynomial time?

Much progress on this problem was made in 2004 by Candes-Tao, Donoho and others, including Rudelson-Vershynin. See our joint FOCS presentation Candes-Tao-Rudelson-Vershynin; also papers by Muthukrishnan and the Compressed Sensing Page. The reconstruction problem has been solved via linear programming, this beautiful idea going back to Donoho and his collaborators. Due to the development of interior point methods in the 1980s, the complexity of the linear program is polynomial in d. Howeverm this might be too slow in applications, especially when d is very large (in streaming algorithms, d=2³² is not uncommon). This paper develops faster reconstruction algorithms, whose complexity is polylogarithmic, rather than polynomial, in d.


ABSTRACT

It has recently been observed that sparse and compressible signals can be sketched using very few nonadaptive linear measurements in comparison with the length of the signal.  This sketch can be viewed as an embedding of an entire class of compressible signals into a low-dimensional space.  In particular, d-dimensional signals with m nonzero entries (m-sparse signals) can be embedded in O(m log d) dimensions.  To date, most algorithms for approximating or reconstructing the signal from the sketch, such as the linear programming approach proposed by Candes-Tao and Donoho, require time polynomial in the signal length.

This paper develops new methods for sketching both m-sparse and compressible signals with O(m polylog d) nonadaptive linear measurements.  Two algorithms are developed that can reconstruct the original signal in time O(m polylog d) with an error proportional to the optimal m-term approximation error.  In particular, m-sparse signals are recovered perfectly and compressible signals are recovered with polylogarithmic distortion.  One of the algorithms operates in small space O(m polylog d), so it is appropriate for streaming data.

These sketching techniques and the corresponding reconstruction algorithms can be viewed as uniform algorithmic embeddings of an entire class of signals. In particular, m-sparse signals of length d are embedded into O(m log^2 d) dimensions.  The embedding map is Lipschitz, and its inverse is also Lipschitz.  Therefore, the map preserves the geometry of the signal class, and it is stable under small perturbations in its domain or codomain.

Back to Publications