CS: Friday's ArXiv Batch in Compressed Sensing

Today, we have quite a few papers coming from Arxiv, without further due, here is this week-end reading list:

Sequential Analysis in High Dimensional Multiple Testing and Sparse Recovery by Matt Malloy, Robert Nowak. The abstract reads:

This paper studies the problem of high-dimensional multiple testing and sparse recovery from the perspective of sequential analysis. In this setting, the probability of error is a function of the dimension of the problem. A simple sequential testing procedure for this problem is proposed. We derive necessary conditions for reliable recovery in the non-sequential setting and contrast them with sufficient conditions for reliable recovery using the proposed sequential testing procedure. Applications of the main results to several commonly encountered models show that sequential testing can be exponentially more sensitive to the difference between the null and alternative distributions (in terms of the dependence on dimension), implying that subtle cases can be much more reliably determined using sequential methods.

Unicity conditions for low-rank matrix recovery by Yonina C. Eldar, Deanna Needell, Yaniv Plan. The abstract reads:

Low-rank matrix recovery addresses the problem of recovering an unknown low-rank matrix from few linear measurements. Nuclear-norm minimization is a tractible approach with a recent surge of strong theoretical backing. Analagous to the theory of compressed sensing, these results have required random measurements. For example, m >= Cnr Gaussian measurements are sufficient to recover any rank-r n x n matrix with high probability. In this paper we address the theoretical question of how many measurements are needed via any method whatsoever --- tractible or not. We show that for a family of random measurement ensembles, m >= 4nr - 4r^2 measurements are sufficient to guarantee that no rank-2r matrix lies in the null space of the measurement operator with probability one. This is a necessary and sufficient condition to ensure uniform recovery of all rank-r matrices by rank minimization. Furthermore, this value of $m$ precisely matches the dimension of the manifold of all rank-2r matrices. We also prove that for a fixed rank-r matrix, m \gt 2nr - r^2 + 1 random measurements are enough to guarantee recovery using rank minimization. These results give a benchmark to which we may compare the efficacy of nuclear-norm minimization.

On the Certification of the Restricted Isometry Property by Pascal Koiran, Anastasios Zouzias. The abstract reads:

Compressed sensing is a technique for finding sparse solutions to underdetermined linear systems. This technique relies on properties of the sensing matrix such as the restricted isometry property. Sensing matrices that satisfy the restricted isometry property with optimal parameters are mainly obtained via probabilistic arguments. Given any matrix, deciding whether it satisfies the restricted isometry property is a non-trivial computational problem. In this paper, we give reductions from dense subgraph problems to the certification of the restricted isometry property. This gives evidence that certifying the restricted isometry property is unlikely to be feasible in polynomial-time. Moreover, on the positive side we propose an improvement on the brute-force enumeration algorithm for checking the restricted isometry property.

Exact Reconstruction using Support Pursuit by Yohann de Castro, Fabrice Gamboa. The abstract reads:

In this article we show that measures, with finite support on the real line, are the unique solution to an algorithm, named support pursuit, involving only a finite number of generalized moments (which encompass the standard moments, the Laplace transform, the Stieljes transformation, etc...). The support pursuit share related geometric properties with basis pursuit of Chen, Donoho and Saunders. As a matter of fact we extend some standard results of compressed sensing (the dual polynomial, the nullspace property) to the signed measure framework. We express exact reconstruction in terms of a simple interpolation problem. We prove that every nonnegative measure, supported by a set containing s points, can be exactly recovered from only 2s+1 generalized moments. This result leads to a new construction of deterministic sensing matrices for compressed sensing. In particular, we prove that one can recover all nonnegative s-sparse vectors from only 2s+1 linear measurements.

Regularization via Data Augmentation by Nicholas G. Polson, James G. Scott. The abstract reads:

In this paper we provide a data-augmentation scheme that unifies many common regularized estimators into a single class. This leads to simple algorithms based on iterative least squares for fitting models involving arbitrary combinations of likelihood and penalty functions within the class. The class itself is quite large: for example, it includes quantile regression, support vector machines, and logistic and multinomial logistic regression, along with the usual ridge regression, lasso, bridge estimators, and regression with heavy-tailed errors. To arrive at this unified framework, we represent a wide class of objective functions as variance--mean mixtures of Gaussians involving both the likelihood and penalty functions. This generalizes existing theory based solely on variance mixtures for the penalty function, and allows the theory of conditionally normal linear models to be brought to bear on a much wider class of models. We focus on two possible choices of the mixing measures: the generalized inverse-Gaussian and Polya distributions, leading to the hyperbolic and Z distributions, respectively. We exploit this conditional normality to find sparse, regularized estimates using tilted iteratively re-weighted least squares (TIRLS). Finally, we characterize the conditional moments of the latent variances for any model in our proposed class, and show the relationship between our method and two recent algorithms: LQA (local quadratic approximation) and LLA (local linear approximation).

The following papers used compressed sensing as a reference:

• Invertibility of random submatrices via the Non-Commutative Bernstein Inequality by Stéphane Chrétien, Sébastien Darses
• On Understanding and Machine Understanding by Tong Chern
• Clustered regression with unknown clusters, by Kishor Barman, Onkar Dabeer
• Randomized Smoothing for Stochastic Optimization by John C. Duchi, Peter L. Bartlett, Martin J. Wainwright
• Learning the Ambiguity function by Sofia Olhede
• Algebraic reconstruction of piecewise-smooth functions from integral measurements by Dmitry Batenkov, Niv Sarig, Yosef Yomdin
• Inverse polynomial optimization by Jean Lasserre

Image Credit: NASA/Johns Hopkins University Applied Physics Laboratory/Carnegie Institution of Washington, Exploring the Rays of Debussy
Bright rays, consisting of impact ejecta and secondary craters, spread across this NAC image and radiate from Debussy crater, located at the top. The image, acquired yesterday during the first orbit for which MDIS was imaging, shows just a small portion of Debussy's large system of rays in greater detail than ever previously seen. Images acquired during MESSENGER's second Mercury flyby showed that Debussy's rays extend for hundreds of kilometers across Mercury's surface. Debussy crater was named in March 2010, in honor of the French composer Claude Debussy (1862-1918).

Date acquired: March 29, 2011