×

Testing the nullspace property using semidefinite programming. (English) Zbl 1211.90167

Summary: Recent results in compressed sensing show that, under certain conditions, the sparsest solution to an underdetermined set of linear equations can be recovered by solving a linear program. These results either rely on computing sparse eigenvalues of the design matrix or on properties of its nullspace. So far, no tractable algorithm is known to test these conditions and most current results rely on asymptotic properties of random matrices. Given a matrix \(A\), we use semidefinite relaxation techniques to test the nullspace property on \(A\) and show on some numerical examples that these relaxation bounds can prove perfect recovery of sparse solutions with relatively high cardinality.

MSC:

90C22 Semidefinite programming
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
90C27 Combinatorial optimization

Software:

DSPCA; SDPT3; SeDuMi
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Affentranger F., Schneider R.: Random projections of regular simplices. Discrete Comput. Geom. 7(1), 219–226 (1992) · Zbl 0751.52002 · doi:10.1007/BF02187839
[2] Barvinok A.: Integration and optimization of multivariate polynomials by restriction onto a random subspace. Foundations Comput. Math. 7(2), 229–244 (2007) · Zbl 1132.68069 · doi:10.1007/s10208-005-0178-x
[3] Boyd, S., El Ghaoui, L., Feron, E., Balakrishnan, V.: Linear matrix inequalities in system and control theory. SIAM (1994) · Zbl 0816.93004
[4] Candès E., Tao T.: Near-optimal signal recovery from random projections: universal encoding strategies?. IEEE Trans. Inform. Theory 52(12), 5406–5425 (2006) · Zbl 1309.94033 · doi:10.1109/TIT.2006.885507
[5] Candès E.J., Tao T.: Decoding by linear programming. IEEE Trans. Inform. Theory 51(12), 4203–4215 (2005) · Zbl 1264.94121 · doi:10.1109/TIT.2005.858979
[6] Cohen A., Dahmen W., DeVore R.: Compressed sensing and best k-term approximation. J. AMS 22(1), 211–231 (2009) · Zbl 1206.94008
[7] d’Aspremont A., El Ghaoui L., Jordan M., Lanckriet G.R.G.: A direct formulation for sparse PCA using semidefinite programming. SIAM Rev. 49(3), 434–448 (2007) · Zbl 1128.90050 · doi:10.1137/050645506
[8] d’Aspremont A., Bach F., El Ghaoui L.: Optimal solutions for sparse principal component analysis. J. Mach. Learn. Res. 9, 1269–1294 (2008) · Zbl 1225.68170
[9] Donoho D., Huo X.: Uncertainty principles and ideal atomic decomposition. IEEE Trans. Inform. Theory 47(7), 2845–2862 (2001) · Zbl 1019.94503 · doi:10.1109/18.959265
[10] Donoho D., Tanner J.: Counting the faces of randomly-projected hypercubes and orthants, with applications. Arxiv Preprint arXiv, 08073590 (2008) · Zbl 1191.52004
[11] Donoho D.L., Tanner J.: Sparse nonnegative solutions of underdetermined linear equations by linear programming. Proc. Natl. Acad. Sci. 102(27), 9446–9451 (2005) · Zbl 1135.90368 · doi:10.1073/pnas.0502269102
[12] Goemans M., Williamson D.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J ACM 42, 1115–1145 (1995) · Zbl 0885.68088 · doi:10.1145/227683.227684
[13] Ibragimov, I., Sudakov, V., Tsirelson, B.: Norms of Gaussian sample functions. In: Proceedings of the third Japan USSR symposium on probability theory, lecture notes in math, vol. 550, pp. 20–41 (1976)
[14] Juditsky, A., Nemirovski, A.: On verifiable sufficient conditions for sparse signal recovery via 1 minimization. ArXiv 08092650 (2008) · Zbl 1211.90333
[15] Lee, K., Bresler, Y.: Computing performance guarantees for compressed sensing. In: IEEE International Conference on Acoustics, Speech and Signal Processing, 2008. ICASSP 2008, pp 5129–5132 (2008)
[16] Massart, P.: Concentration inequalities and model selection. Ecole d’Eté de Probabilités de Saint-Flour XXXIII (2007) · Zbl 1170.60006
[17] Moler C., Van Loan C.: Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later. SIAM Rev. 45(1), 3–49 (2003) · Zbl 1030.65029 · doi:10.1137/S00361445024180
[18] Nesterov Y.: Introductory Lectures on Convex Optimization. Springer, Heidelberg (2003) · Zbl 1086.90045
[19] Nesterov Y.: Smooth minimization of non-smooth functions. Math. Program. 103(1), 127–152 (2005) · Zbl 1079.90102 · doi:10.1007/s10107-004-0552-5
[20] Nesterov Y.: Smoothing technique and its applications in semidefinite optimization. Math. Program. 110(2), 245–259 (2007) · Zbl 1126.90058 · doi:10.1007/s10107-006-0001-8
[21] Sturm J.: Using SEDUMI 1.0x, a MATLAB toolbox for optimization over symmetric cones. Optim. Method. Sofw. 11, 625–653 (1999) · Zbl 0973.90526 · doi:10.1080/10556789908805766
[22] Toh K.C., Todd M.J., Tutuncu R.H.: SDPT3–a MATLAB software package for semidefinite programming. Optim. Method. Sofw. 11, 545–581 (1999) · Zbl 0997.90060 · doi:10.1080/10556789908805762
[23] Vershik A., Sporyshev P.: Asymptotic behavior of the number of faces of random polyhedra and the neighborliness problem. Selecta Math Soviet 11(2), 181–201 (1992) · Zbl 0791.52011
[24] Zhang Y.: A simple proof for recoverability of 1-minimization: Go over or under. Rice University CAAM Technical report TR05-09 (2005)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.