# zbMATH — the first resource for mathematics

Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods. (English) Zbl 1353.65057
Summary: We propose two approaches to solve large-scale compressed sensing problems. The first approach uses the parametric simplex method to recover very sparse signals by taking a small number of simplex pivots, while the second approach reformulates the problem using Kronecker products to achieve faster computation via a sparser problem formulation. In particular, we focus on the computational aspects of these methods in compressed sensing. For the first approach, if the true signal is very sparse and we initialize our solution to be the zero vector, then a customized parametric simplex method usually takes a small number of iterations to converge. Our numerical studies show that this approach is 10 times faster than state-of-the-art methods for recovering very sparse signals. The second approach can be used when the sensing matrix is the Kronecker product of two smaller matrices. We show that the best-known sufficient condition for the Kronecker compressed sensing (KCS) strategy to obtain a perfect recovery is more restrictive than the corresponding condition if using the first approach. However, KCS can be formulated as a linear program with a very sparse constraint matrix, whereas the first approach involves a completely dense constraint matrix. Hence, algorithms that benefit from sparse problem representation, such as interior point methods (IPMs), are expected to have computational advantages for the KCS problem. We numerically demonstrate that KCS combined with IPMs is up to 10 times faster than vanilla IPMs and state-of-the-art methods such as $$\ell_1\_\ell_s$$ and Mirror Prox regardless of the sparsity level or problem size.

##### MSC:
 65K05 Numerical mathematical programming methods 90C05 Linear programming 90C51 Interior-point methods 90C06 Large-scale problems in mathematical programming 94A12 Signal theory (characterization, reconstruction, filtering, etc.)
##### Software:
ALPO; CoSaMP; l1_ls; LOQO; LPbook; Matlab; PDCO
Full Text:
##### References:
 [1] Adler, I; Karp, RM; Shamir, R, A simplex variant solving an $$m× d$$ linear program in $${O}(\min (m_2, d_2)$$ expected number of pivot steps, J. Complex., 3, 372-387, (1987) · Zbl 0641.65054 [2] Belloni, A; Chernozhukov, V, $$ℓ _1$$-penalized quantile regression in high-dimensional sparse models, Ann. Stat., 39, 82-130, (2011) · Zbl 1209.62064 [3] Cai, T.T., Zhang, A.: Sharp RIP bound for sparse signal and low-rank matrix recovery. Appl. Comput. Harmonic Anal. 35, 74-93 (2012) · Zbl 1310.94021 [4] Candès, E; 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 [5] Candès, EJ, The restricted isometry property and its implications for compressed sensing, C. R. Math., 346, 589-592, (2008) · Zbl 1153.94002 [6] Chen, SS; Donoho, DL; Saunders, MA, Atomic decomposition by basis pursuit, SIAM J. Sci. Comput., 20, 33-61, (1998) · Zbl 0919.94002 [7] Cohen, A; Dahmen, W; Devore, R, Compressed sensing and best $$k$$-term approximation, J. Am. Math. Soc., 22, 211-231, (2009) · Zbl 1206.94008 [8] Dantzig, G.B.: Linear Programming and Extensions. Princeton University Press, Princeton (1998) · Zbl 0997.90504 [9] Donoho, DL, Compressed sensing, IEEE Trans. Inf. Theory, 52, 1289-1306, (2006) · Zbl 1288.94016 [10] Donoho, DL; Elad, M, Optimally sparse representation in general (nonorthogonal) dictionaries via $$ℓ _1$$-minimization, Proc. Natl. Acad. Sci USA, 100, 2197-2202, (2003) · Zbl 1064.94011 [11] Donoho, DL; Elad, M; Temlyakov, VN, Stable recovery of sparse overcomplete representations in the presence of noise, IEEE Trans. Inf. Theory, 52, 6-18, (2006) · Zbl 1288.94017 [12] Donoho, DL; Huo, X, Uncertainty principles and ideal atomic decomposition, IEEE Trans. Inf. Theory, 47, 2845-2862, (2001) · Zbl 1019.94503 [13] Donoho, DL; Maleki, A; Montanari, A, Message passing algorithms for compressed sensing, Proc. Natl. Acad. Sci. USA, 106, 18914-18919, (2009) [14] Donoho, DL; Stark, PB, Uncertainty principles and signal recovery, SIAM J. Appl. Math., 49, 906-931, (1989) · Zbl 0689.42001 [15] Donoho, D.L., Tanner, J.: Neighborliness of randomly projected simplices in high dimensions. Proc. Natl. Acad. Sci. 102, 9452-9457 (2005) · Zbl 1135.60300 [16] Donoho, D. L., Tanner, J.: Sparse nonnegative solutions of underdetermined linear equations by linear programming. Proc. Natl. Acad. Sci. 102, 9446-9451 (2005) · Zbl 1135.90368 [17] Donoho, DL; Tanner, J, Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing, Philos. Trans. Roy. Soc. S. A, 367, 4273-4273, (2009) · Zbl 1185.94029 [18] Duarte, MF; Baraniuk, RG, Kronecker compressive sensing, IEEE Trans. Image Process., 21, 494-504, (2012) · Zbl 1372.94379 [19] Elad, M.: Sparse and Redundant Representations—From Theory to Applications in Signal and Image Processing. Springer, New York (2010) · Zbl 1211.94001 [20] Figueiredo, M; Nowak, R; Wright, S, Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems, IEEE J. Sel. Top. Signal Process., 1, 586-597, (2008) [21] Forrest, JJ; Goldfarb, D, Steepest-edge simplex algorithms for linear programming, Math. Program., 57, 341-374, (1992) · Zbl 0787.90047 [22] Foucart, S, Hard thresholding pursuit: an algorithm for compressive sensing, SIAM J. Numer. Anal., 49, 2543-2563, (2011) · Zbl 1242.65060 [23] Foucart, S., Rauhut, H.: A Mathematical Introduction to Compressive Sensing. Springer, New York (2013) · Zbl 1315.94002 [24] Gilbert, A.C., Strauss, M.J., Tropp, J.A., Vershynin, R.: One sketch for all: fast algorithms for compressed sensing. In: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pp. 237-246. ACM, New York (2007) · Zbl 1232.94008 [25] Gill, P.E., Murray, W., Ponceleon, D.B., Saunders, M.A.: Solving reduced KKT systems in barrier methods for linear and quadratic programming. Tech. rep, DTIC Document (1991) · Zbl 0815.65080 [26] Iwen, MA, Combinatorial sublinear-time Fourier algorithms, Found. Comut. Math., 10, 303-338, (2010) · Zbl 1230.65145 [27] Juditsky, A., Karzan, F.K., Nemirovski, A.: $$ℓ _1$$ minimization via randomized first order algorithms. Université Joseph Fourier, Tech. rep. (2014) · Zbl 1282.90128 [28] Kim, S; Koh, K; Lustig, M; Boyd, S; Gorinevsky, D, An interior-point method for large-scale $$l_1$$-regularized least squares, IEEE Trans. Sel. Top. Signal Process., 1, 606-617, (2007) [29] Klee, V., Minty, G. J.: How good is the simplex method? Inequalities-III, pp. 159-175 (1972) · Zbl 0297.90047 [30] Kutyniok, G.: Compressed sensing: theory and applications. CoRR . arXiv:1203.3815 (2012) · Zbl 1064.94011 [31] Lustig, IJ; Mulvey, JM; Carpenter, TJ, Formulating two-stage stochastic programs for interior point methods, Oper. Res., 39, 757-770, (1991) · Zbl 0739.90048 [32] Mallat, S; Zhang, Z, Matching pursuits with time-frequency dictionaries, Signal Process. IEEE Trans., 41, 3397-3415, (1993) · Zbl 0842.94004 [33] Needell, D; Tropp, JA, Cosamp: iterative signal recovery from incomplete and inaccurate samples, Commun. ACM, 53, 93-100, (2010) · Zbl 1163.94003 [34] Needell, D; Vershynin, R, Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit, Found. Comut. Math., 9, 317-334, (2009) · Zbl 1183.68739 [35] Pan, P-Q, A largest-distance pivot rule for the simplex algorithm, Eur. J. Oper. Res., 187, 393-402, (2008) · Zbl 1149.90101 [36] Post, I; Ye, Y, The simplex method is strongly polynomial for deterministic Markov decision processes, Math. Oper. Res., 40, 859-868, (2015) · Zbl 1329.90084 [37] Spielman, DA; Teng, S-H, Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time, J. ACM (JACM), 51, 385-463, (2004) · Zbl 1192.90120 [38] Tropp, JA, Greed is good: algorithmic results for sparse approximation, IEEE Trans. Inf. Theory, 50, 2231-2242, (2004) · Zbl 1288.94019 [39] Vanderbei, R, Splitting dense columns in sparse linear systems, Linear Algebra Appl., 152, 107-117, (1991) · Zbl 0727.65034 [40] Vanderbei, R, LOQO: an interior point code for quadratic programming, Optim. Methods Softw., 12, 451-484, (1999) · Zbl 0973.90518 [41] Vanderbei, R.: Linear Programming: Foundations and Extensions, 3rd edn. Springer, New York (2007) · Zbl 0874.90133 [42] Vanderbei, RJ, Alpo: another linear program optimizer, ORSA J. Comput., 5, 134-146, (1993) · Zbl 0777.90031 [43] Vanderbei, R. J.: Linear programming. Foundations and extensions, International Series in Operations Research & Management Science, vol. 37 (2001) · Zbl 1043.90002 [44] Vanderbei, RJ, Fast Fourier optimization, Math. Prog. Comp., 4, 1-17, (2012) · Zbl 1257.90049 [45] Yin, W; Osher, S; Goldfarb, D; Darbon, J, Bregman iterative algorithms for $$ℓ _1$$-minimization with applications to compressed sensing, SIAM J. Imaging Sci., 1, 143-168, (2008) · Zbl 1203.90153
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.