Near-Optimal Estimation of Simultaneously Sparse and Low-Rank Matrices from Nested Linear Measurements

 

 

Both figures are from Simultaneously Structured Models with Application to Sparse and Low-rank Matrices by Samet Oymak, Amin Jalali, Maryam Fazel, Yonina C. Eldar, Babak Hassibi.

Back a while ago, it was mentioned that the use of Multiple regularizers may not yield a good enough way to reduce sampling bounds while at the same time enforcing different prior information on the structure of the signal - see the video Convex Relaxations for Recovering Simultaneously Structured Objects and attendant preprint - . During COLT, Maryam pointed me to another approach featured in the following new preprint. In their approach, they had a non convex regularizer, here the approach is to use  nested measurement ensembles.

 

Near-Optimal Estimation of Simultaneously Sparse and Low-Rank Matrices from Nested Linear Measurements by Sohail Bahmani, Justin Romberg

In this paper we consider the problem of estimating simultaneously low-rank and row-wise sparse matrices from nested linear measurements where the linear operator consists of the product of a linear operator W and a matrix Ψ. Leveraging the nested structure of the measurement operator, we propose a computationally efficient two-stage algorithm for estimating the simultaneously structured target matrix. Assuming that W is a restricted isometry for low-rank matrices and Ψ is a restricted isometry for row-wise sparse matrices, we establish an accuracy guarantee that holds uniformly for all sufficiently low-rank and row-wise sparse matrices with high probability. Furthermore, using standard tools from information theory, we establish a minimax lower bound for estimation of simultaneously low-rank and row-wise sparse matrices from linear measurements that need not be nested. The accuracy bounds established for the algorithm, that also serve as a minimax upper bound, differ from the derived minimax lower bound merely by a polylogarithmic factor of the dimensions. Therefore, the proposed algorithm is nearly minimax optimal. We also discuss some applications of the proposed observation model and evaluate our algorithm through numerical simulation.

related: Saturday Morning Videos : Semidefinite Optimization, Approximation and Applications (Simons Institute @ Berkeley)

 

Thanks Maryam for the heads-up ! 

  Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.