×

zbMATH — the first resource for mathematics

Necessary and sufficient conditions of solution uniqueness in 1-norm minimization. (English) Zbl 1308.65102
With a given solution to a 1-norm minimization problem, based on the fact that a pair of feasible primal-dual linear programs has strict complementary solutions, the authors provide a necessary and sufficient condition for guaranteeing recovering that solution uniquely. Some ways on numerically recognizing unique solutions and verifying solution uniqueness are discussed.

MSC:
65K05 Numerical mathematical programming methods
90C25 Convex programming
Software:
L1TestPack; PDCO
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Efron, B; Hastie, T; Johnstone, I; Tibshirani, R, Least angle regression, Ann. Stat., 32, 407-499, (2004) · Zbl 1091.62054
[2] Best, MJ; Grauer, RR, Sensitivity analysis for Mean-variance portfolio problems, Manag. Sci., 37, 980-989, (1991) · Zbl 0729.90857
[3] Donoho, DL; Elad, M, Optimally sparse representation in general (nonorthogonal) dictionaries via \(ℓ _1\) minimization, Proc. Natl. Acad. Sci., 100, 2197-2202, (2003) · Zbl 1064.94011
[4] Bruckstein, AM; Donoho, DL; Elad, M, From sparse solutions of systems of equations to sparse modeling of signals and images, SIAM Rev., 51, 34-81, (2009) · Zbl 1178.68619
[5] Donoho, DL; Huo, X, Uncertainty principles and ideal atomic decomposition, IEEE Trans. Inf. Theory, 47, 2845-2862, (2001) · Zbl 1019.94503
[6] Elad, M; Bruckstein, AM, A generalized uncertainty principle and sparse representation in pairs of bases, IEEE Trans. Inf. Theory, 48, 2558-2567, (2002) · Zbl 1062.15001
[7] Donoho, DL, Compressed sensing, IEEE Trans. Inf. Theory, 52, 1289-1306, (2006) · Zbl 1288.94016
[8] Cohen, A; Dahmen, W; DeVore, R, Compressed sensing and best \(k\)-term approximation, J. Am. Math. Soc., 22, 211-231, (2009) · Zbl 1206.94008
[9] Candes, EJ; Tao, T, Decoding by linear programming, IEEE Trans. Inf. Theory, 51, 4203-4215, (2005) · Zbl 1264.94121
[10] Zhang, Y, Theory of compressive sensing via \(ℓ _1\)-minimization: a non-RIP analysis and extensions, J. Oper. Res. Soc. China, 1, 79-105, (2008) · Zbl 1288.65091
[11] Candes, EJ; Plan, Y, A probabilistic and ripless theory of compressed sensing, IEEE Trans. Inf. Theory, 57, 7235-7254, (2011) · Zbl 1365.94174
[12] Chvatal, V.: Linear Programming. W.H. Freeman and Company, New York (1983) · Zbl 0537.90067
[13] Chen, SS; Donoho, DL; Saunders, MA, Atomic decomposition by basis pursuit, SIAM J. Sci. Comput., 20, 33-61, (1998) · Zbl 0919.94002
[14] Tibshirani, R, Regression shrinkage and selection via the LASSO, J. R. Stat. Soc. Ser. B (Methodological), 58, 267-288, (1996) · Zbl 0850.62538
[15] Fuchs, JJ, On sparse representations in arbitrary redundant bases, IEEE Trans. Inf. Theory, 50, 1341-1344, (2004) · Zbl 1284.94018
[16] Candès, E; Recht, B, Simple bounds for recovering low-complexity models, Math. Program., 141, 577-589, (2013) · Zbl 1278.15038
[17] Candès, EJ; Romberg, J; Tao, T, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory, 52, 489-509, (2006) · Zbl 1231.94017
[18] Tropp, JA, Recovery of short, complex linear combinations via \(ℓ _1\) minimization, IEEE Trans. Inf. Theory, 51, 1568-1570, (2005) · Zbl 1288.94020
[19] Grasmair, M; Scherzer, O; Haltmeier, M, Necessary and sufficient conditions for linear convergence of \(ℓ _1\)-regularization, Commun. Pure Appl. Math., 64, 161-182, (2011) · Zbl 1217.65095
[20] Dossal, C, A necessary and sufficient condition for exact sparse recovery by \(ℓ _1\) minimization, Comptes Rendus Mathematique, 350, 117-120, (2012) · Zbl 1236.94028
[21] Fuchs, JJ, Recovery of exact sparse representations in the presence of bounded noise, IEEE Trans. Inf. Theory, 51, 3601-3608, (2005) · Zbl 1286.94031
[22] Tibshirani, RJ, The LASSO problem and uniqueness, Electron. J.Stat., 7, 1456-1490, (2013) · Zbl 1337.62173
[23] Dantzig, G.B.: Linear Programming and Extensions. Princeton university press, Princeton, NJ (1998) · Zbl 0997.90504
[24] Güler, O; Ye, Y, Convergence behavior of interior-point algorithms, Math. Program., 60, 215-228, (1993) · Zbl 0803.90087
[25] Lorenz, DA, Constructing test instances for basis pursuit denoising, IEEE Trans. Signal Process., 61, 1210-1214, (2013) · Zbl 1393.94345
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.