Weak Recovery Conditions from Graph Partitioning Bounds and Order Statistics

References

• Abramowitz M, Stegun I. Handbook of Mathematical Functions (1970) (Dover, New York) Google Scholar
• Affentranger F, Schneider R. Random projections of regular simplices. Discrete Comput. Geometry (1992) 7(1):219–226Crossref, Google Scholar
• Arora S, Karger D, Karpinski M. Polynomial time approximation schemes for dense instances of NP-hard problems. Proc. of 27th ACM Symposium on Theory of Computing (STOC) (1995) (ACM Press, New York) 193–210Google Scholar
• Baraniuk R, Davenport M, DeVore R, Wakin M. A simple proof of the restricted isometry property for random matrices. Constructive Approximation (2008) 28(3):253–263Crossref, Google Scholar
• Ben-Tal A, El Ghaoui L, Nemirovski AS. Robust Optimization (2009) (Princeton University Press, Princeton, NJ) Crossref, Google Scholar
• Bickel PJ, Ritov Y, Tsybakov AB. Simultaneous analysis of lasso and Dantzig selector. Ann. Statist. (2007) 37(4):1705–1732Crossref, Google Scholar
• Billionnet A, Roupin F. A deterministic approximation algorithm for the densest k-subgraph problem. Internat. J. Oper. Res. (2006) 3(3):301–314Google Scholar
• Candes E, Tao T. The Dantzig selector: Statistical estimation when p is much larger than n. Ann. Statist. (2007) 35(6):2313–2351Crossref, Google Scholar
• Candès EJ, Plan Y. Near-ideal model selection by 𝓁1 minimization. Ann. Statist. (2009) 37(5A):2145–2177Crossref, Google Scholar
• Candès EJ, Tao T. Decoding by linear programming. IEEE Trans. Inform. Theory (2005) 51(12):4203–4215Crossref, Google Scholar
• Candès EJ, Tao T. Near-optimal signal recovery from random projections: Universal encoding strategies? IEEE Trans. Inform. Theory (2006) 52(12):5406–5425Crossref, Google Scholar
• Cohen A, Dahmen W, DeVore R. Compressed sensing and best k-term approximation. J. AMS (2009) 22(1):211–231Google Scholar
• d'Aspremont A, Bach F, El Ghaoui L. Optimal solutions for sparse principal component analysis. J. Machine Learn. Res. (2008) 9:1269–1294Google Scholar
• d'Aspremont A, El Ghaoui L. Testing the nullspace property using semidefinite programming. Math. Programming (2011) 127:123–144Crossref, Google Scholar
• Davidson KR, Szarek SJ, Johnson WB, Lindenstranss J. Local operator theory, random matrices and Banach spaces. Handbook of the Geometry of Banach Spaces (2001) 1(Elsevier, Amsterdam) 317–366Crossref, Google Scholar
• Donoho DL. Neighborly polytopes and sparse solution of underdetermined linear equations. (2004) . Stanford Dept. of Statistics Working paper, Stanford, CAGoogle Scholar
• Donoho DL. Compressed sensing. IEEE Trans. Inform. Theory (2006) 52(4):1289–1306Crossref, Google Scholar
• Donoho DL, Huo X. Uncertainty principles and ideal atomic decomposition. IEEE Trans. Inform. Theory (2001) 47(7):2845–2862Crossref, Google Scholar
• Donoho DL, Tanner J. Sparse nonnegative solutions of underdetermined linear equations by linear programming. Proc. Natl. Acad. Sci. (2005) 102(27):9446–9451Crossref, Google Scholar
• Donoho DL, Tanner J. Counting the faces of randomly-projected hypercubes and orthants, with applications. Discrete Computational Geometry (2008) 43(3):522-541Google Scholar
• Feige U, Langberg M. Approximation algorithms for maximization problems arising in graph partitioning. J. Algorithms (2001) 41(2):174–211Crossref, Google Scholar
• Feige U, Seltser M. On the densest k-subgraph problem. (1997) . Technical report, Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot, IsraelGoogle Scholar
• Feige U, Peleg D, Kortsarz G. The dense k-subgraph problem. Algorithmica (2001) 29(3):410–421Crossref, Google Scholar
• Goemans MX, Williamson DP. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM (1995) 42:1115–1145Crossref, Google Scholar
• Han Q, Ye Y, Zhang J. An improved rounding method and semidefinite programming relaxation for graph partition. Math. Programming (2002) 92(3):509–535Crossref, Google Scholar
• Helmberg C, Rendl F, Weismantel R. A semidefinite programming approach to the quadratic knapsack problem. J. Combinatorial Optim. (2000) 4(2):197–215Crossref, Google Scholar
• Juditsky A, Nemirovski AS. On verifiable sufficient conditions for sparse signal recovery via 𝓁1 minimization. Math. Programming Series B (2011) 127:57–88Crossref, Google Scholar
• Kortsarz G, Peleg D. On choosing a dense subgraph. Foundations of Comput. Sci., 1993. Proc., 34th Annual Sympos. (1993) (IEEE Computer Society, Washington, D.C.) 692–701Google Scholar
• Ledoux M. The Concentration of Measure Phenomenon (2005) (American Mathematical Society, Providence, RI) Crossref, Google Scholar
• Lin EYH. A biblographical survey on some well-known non-standard knapsack problems. Inform. Systems Oper. Res. (1998) 36(4):274–317Google Scholar
• Massart P. Concentration Inequalities and Model Selection (2007) (Springer-Verlag, Berlin) Ecole d'Eté de Probabilités de Saint-Flour XXXIIIGoogle Scholar
• Meinshausen N, Yu B. Lasso-type recovery of sparse representations for high-dimensional data. Ann. Statist. (2008) 37(1):246–270Crossref, Google Scholar
• Meinshausen N, Rocha G, Yu B. A tale of three cousins: Lasso, l2boosting, and Dantzig. Ann. Statist. (2007) 35(6):2373–2384Crossref, Google Scholar
• Nemirovski AS. The matrix cube problem: Approximations and applications (2001) . http://2.isye.gatech.edu/∼nemirous/st_talk.pdfGoogle Scholar
• Nemirovski AS. Computation of matrix norms with applications to robust optimization. (2005) . Ph.D. thesis, Technion, Haifa, IsraelGoogle Scholar
• Nesterov Y. Global quadratic optimization via conic relaxation (1998a) . 9860, CORE Discussion PaperGoogle Scholar
• Nesterov Y. Semidefinite relaxation and nonconvex quadratic optimization. Optim. Methods Software (1998b) 9(1):141–160Crossref, Google Scholar
• Nesterov Y. Smoothing technique and its applications in semidefinite optimization. Math. Programming (2007) 110(2):245–259Crossref, Google Scholar
• Pisinger D. The quadratic knapsack problem—A survey. Discrete Appl. Math. (2007) 155(5):623–648Crossref, Google Scholar
• Srivastav A, Wolf K. Finding dense subgraphs with semidefinite programming. Approximation Algorithms for Combinatiorial Optimization (1998) 1444(Springer-Verlag, Berlin) 181–192Lecture Notes Computer ScienceCrossref, Google Scholar
• Tibshirani R. Regression shrinkage and selection via the LASSO. J. Roy. Statist. Soc., Ser. B (1996) 58(1):267–288Crossref, Google Scholar
• Vershik AM, Sporyshev PV. Asymptotic behavior of the number of faces of random polyhedra and the neighborliness problem. Selecta Math. Soviet (1992) 11(2):181–201Google Scholar
• Zhang Y. A simple proof for recoverability of 𝓁1-minimization: Go over or under. (2005) . Rice University CAAM Technical Report TR05-09, Rice University, Houston, TXGoogle Scholar
• Zhao P, Yu B. On model selection consistency of lasso. J. Machine Learn. Res. (2006) 7:2541–2563Google Scholar