2012

Simultaneously Structured Models with Application to Sparse and Low-rank Matrices

Oymak, Samet, Jalali, Amin, Fazel, Maryam et al.

Understand

The topic of recovery of a structured model given a small number of linear observations has been well-studied in recent years.

Examples include recovering sparse or group-sparse vectors, low-rank matrices, and the sum of sparse and low-rank matrices, among others.
In various applications in signal processing and machine learning, the model of interest is known to be structured in several ways at the same time, for example, a matrix that is simultaneously sparse and low-rank.
Often norms that promote each individual structure are known, and allow for recovery using an order-wise optimal number of measurements (e.g., $\ell_1$ norm for sparsity, nuclear norm for matrix rank).

Built on

J.J. Moreau, “Décomposition orthogonale d’un espace Hilbertien selon deux cones mutuellement polaires”. C. R. Acad. Sci., volume 255, pages 238–240, 1962
1962
Earlier work this paper cites.
A. Walther. “The question of phase retrieval in optics”. Opt. Acta, 10:41–49, 1963
1963
Earlier work this paper cites.
L. Tucker. Some mathematical notes on three-mode factor analysis. Psychometrika, 31(3):279-311, 1966
1966
Earlier work this paper cites.
R.W. Gerchberg and W.O. Saxton, “Phase retrieval by iterated projections”, Optik 35, 237, 1972
1972
Earlier work this paper cites.
J.R. Fienup, “Phase retrieval algorithms: a comparison”, Applied Optics 21, 2758-2769, 1982
1982
Earlier work this paper cites.
Y. Gordon, “On Milman’s inequality and random subspaces which escape through a mesh in ℝ n \mathbb{R}^{n} ”. Geometric aspects of functional analysis, Isr. Semin. 1986-87, Lect. Notes Math. 1317, 84-106. (1988)
1988
Earlier work this paper cites.
N. Hurt. “Phase retrieval and zero crossings”, Kluwer Academic Publishers, Norwell, MA, 1989
1989
Earlier work this paper cites.
R.P. Millane, “Phase retrieval in crystallography and optics”. J. Opt. Soc. Am. A 7, 394-411 (1990)
1990
Earlier work this paper cites.
G.A. Watson, “Characterization of the subdifferential of some matrix norms”. Linear Algebra and its Appl. 170, 33–45 (1992)
1992
Earlier work this paper cites.
R.W. Harrison, “Phase problem in crystallography”. J. Opt. Soc. Am. A, 10(5):1045–1055, 1993
1993
Earlier work this paper cites.
Z. Bai and Y. Yin, “Limit of the smallest eigenvalue of a large-dimensional sample covariance matrix”, Annals of Probability, 21, 1275–1294 (1993)
1993
Earlier work this paper cites.
R.T. Rockafellar, “Convex Analysis”. Princeton University Press, 1997
1997
Earlier work this paper cites.
J.F. Sturm, “Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones,” 1998
1998
Earlier work this paper cites.
D. Bertsekas with A. Nedic and A.E. Ozdaglar, “Convex Analysis and Optimization” Athena Scientific, 2003
2003
Earlier work this paper cites.
S. Boyd and L. Vandenberghe, “Convex Optimization”. Cambridge University Press, 2004
2004
Earlier work this paper cites.
R.T. Rockafellar, R. J-B Wets, “Variational Analysis”. Springer, 2004
2004
Earlier work this paper cites.

Similar

D. L. Donoho and J. Tanner. “Sparse nonnegative solution of underdetermined linear equations by linear programming.” Proceedings of the National Academy of Sciences of the United States of America 102.27 (2005): 9446-9451
2005
Cited alongside, same era.
R. Tibshirani, M. Saunders, S. Rosset, J. Zhu, and K. Knight. “Sparsity and smoothness via the fused lasso.” Journal of the Royal Statistical Society: Series B (Statistical Methodology) 67, no. 1 (2005): 91-108
2005
Cited alongside, same era.
D.L. Donoho, “Compressed sensing,” IEEE Trans. Inform. Theory, 52(4):1289-1306, 2006
2006
Cited alongside, same era.
E.J. Candes, JK Romberg and T Tao, “Stable signal recovery from incomplete and inaccurate measurements”. Comm. on Pure and Applied Math. Vol. 59, Issue 8, pg 1207Ð1223, August 2006
2006
Cited alongside, same era.
M. Yuan and Y. Lin, ÒModel selection and estimation in regression with grouped variables,Ó J. Roy. Stat. Soc. Ser. B Stat. Methodol., vol. 68, no. 1, pp. 49Ð67, 2006
2006
Cited alongside, same era.
J. A. Tropp “On the conditioning of random subdictionaries.” Applied and Computational Harmonic Analysis 25.1 (2008): 1–24
2008
Cited alongside, same era.
A. d’Aspremont, F. Bach, L. El Ghaoui. “Optimal Solutions for Sparse Principal Component Analysis”, Journal of Machine Learning Research, 9(Jul):1269Ð1294, 2008
2008
Cited alongside, same era.
B. Recht, M. Fazel, P. Parrilo, “Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization”. SIAM Review, Vol 52, no 3, pages 471-501, 2010
2010
Cited alongside, same era.
M. Stojnic, F. Parvaresh, and B. Hassibi, ÒOn the reconstruction of block-sparse signals with an optimal number of measurements,Ó IEEE Trans. Signal Process., vol. 57, no. 8, pp. 3075Ð3085, May 2010
2010
Cited alongside, same era.
M. Journée, Y. Nesterov, P. Richtárik, and R Sepulchre, “Generalized Power Method for Sparse Principal Component Analysis”. Journal of Machine Learning Research 11 (2010) 517–553
2010
Cited alongside, same era.
S. Gandy, B. Recht, and I. Yamada, “Tensor completion and low-n-rank tensor recovery via convex optimization”, Inverse Problems 27(2), 025010 (2011)
2011
Cited alongside, same era.
E. J. Candes, and Y. Plan. “A probabilistic and RIPless theory of compressed sensing.” Information Theory, IEEE Transactions on 57.11 (2011): 7235-7254
2011
Cited alongside, same era.

Then

E.J. Candès, Y.C. Eldar, T. Strohmer and V. Voroninski, “Phase retrieval via matrix completion”, arXiv:1109.0573, Sep. 2011
Original
2011
Later among the works it cites.
Golbabaee, M., and Vandergheynst, P. (2012, September). Joint trace/TV norm minimization: A new efficient approach for spectral compressive imaging. In Image Processing (ICIP), 2012 19th IEEE International Conference on (pp. 933-936). IEEE
2012
Closest in time.
A. Agarwal, S. Negahban, M. J. Wainwright, “Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions,” Annals of Statistics, Volume 40, Number 2 (2012), 1171-1197
2012
Closest in time.
M. Golbabaee and P. Vandergheynst, “Hyperspectral image compressed sensing via low-rank and joint-sparse matrix recovery”. ICASSP 2012
2012
Closest in time.
H. Ohlsson, A. Y. Yang, R. Dong, S. S. Sastry, “Compressive phase retrieval from squared output measurements via semidefinite programming”, arXiv:1111.6323v3 , March 2012
Original
2012
Closest in time.
K. Jaganathan, S. Oymak, and B. Hassibi, “Recovery of sparse 1-D signals from the magnitudes of their Fourier transform”, arXiv:1206.1405v1, June 2012
Original
2012
Closest in time.
Y. Shechtman and A. Beck and Y.C. Eldar, “Efficient Phase Retrieval of Sparse Signals”. IEEI 2012
2012
Closest in time.
Y.C. Eldar and S. Mendelson ”Phase Retrieval: Stability and Recovery Guarantees”, Arxiv:1211.0872, Nov. 2012
Original
2012
Closest in time.
CVX Research, Inc. “CVX: Matlab software for disciplined convex programming”, version 2.0 beta. http://cvxr.com/cvx, September 2012
2012
Closest in time.
D. Needell and R. Ward. “Stable image reconstruction using total variation minimization.” SIAM Journal on Imaging Sciences 6.2 (2013): 1035-1058
2013
Closest in time.
Grasedyck, Lars, Daniel Kressner, and Christine Tobler. “A literature survey of low?rank tensor approximation techniques.” GAMM?Mitteilungen 36.1 (2013): 53–78
2013
Closest in time.
Liu, Ji, et al. “Tensor completion for estimating missing values in visual data.” Pattern Analysis and Machine Intelligence, IEEE Transactions on 35.1 (2013): 208-220
2013
Closest in time.
Semerci, O., Hao, N., Kilmer, M. E., and Miller, E. L. (2013). Tensor-based formulation and nuclear norm regularization for multi-energy computed tomography. arXiv preprint arXiv:1307.5348
Original
2013
Closest in time.
D. Amelunxen, M. Lotz, M. B. McCoy, and J. A. Tropp. “Living on the edge: Phase transitions in convex programs with random data.” Inform. Inference (2014)
2014
Closest in time.
R. Foygel and L. Mackey. “Corrupted sensing: Novel guarantees for separating structured signals,” Information Theory, IEEE Transactions on 60.2 (2014): 1223–1247
2014
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…