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, <i>d</i>-dimensional signals with
<i>m</i> nonzero entries (<i>m</i>-sparse signals) can be embedded in <i>O</i>(<i>m</i> log <i>d</i>) 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 a new method, called Chaining Pursuit, for sketching both <i>m</i>-sparse and compressible signals with <i>O</i>(<i>m</i> polylog <i>d</i>) nonadaptive linear measurements. The algorithm can reconstruct the original signal in time <i>O</i>(<i>m</i> polylog <i>d</i>) with an error proportional to the optimal <i>m</i>-term approximation error. In particular, <i>m</i>-sparse signals are recovered perfectly and compressible signals are recovered with polylogarithmic distortion. Moreover, the algorithm can operate in small space <i>O</i>(<i>m</i> polylog <i>d</i>), so it is appropriate for streaming data.
Recent work on sparse approximation has focused on the theoretical performance of algorithms for random inputs. This average-case behavior is typically far better than the behavior for the worst inputs. Moreover, an average-case analysis fits naturally with the type of signals that arise in certain applications, such as wireless communications. This paper describes what is currently known about the performance of greedy prusuit algorithms with random inputs. In particular, it gives a new result for the performance of Orthogonal Matching Pursuit (OMP) for sparse signals contaminated with random noise, and it explains recent work on recovering sparse signals from random measurements via OMP. The paper also provides a list of open problems to stimulate further research.
A complex equiangular tight frame (ETF) is a tight frame consisting of N unit vectors in C<sup>d</sup> whose absolute inner products are identical. One may view complex ETFs as a natural geometric generalization of an orthonormal basis. Numerical evidence suggests that these objects do not arise for most pairs (<i>d</i>, N). The goal of this paper is to develop conditions on (<i>d</i>, N) under which complex ETFs can exist. In particular, this work concentrates on the class of harmonic ETFs, in which the components of the frame vectors are roots of unity. In this case, it is possible to leverage field theory to obtain stringent restrictions on the possible values for (<i>d</i>, N).