A Semidefinite Programming Relaxation for the Sparse Integer Least Squares Problem

References

• Adcock B, Hansen AC, Poon C, Roman B (2017) Breaking the coherence barrier: A new theory for compressed sensing. Forum Math. Sigma 5:e4.Google Scholar
• Amini AA, Wainwright MJ (2008) High-dimensional analysis of semidefinite relaxations for sparse principal components. IEEE Internat. Sympos. Inform. Theory (Toronto), 2454–2458.Google Scholar
• ApS M (2020) The MOSEK optimization toolbox for MATLAB manual, version 9.2. Accessed June 1, 2020, https://docs.mosek.com/9.2/toolbox/index.html.Google Scholar
• Barik S, Vikalo H (2014) Sparsity-aware sphere decoding: Algorithms and complexity analysis. IEEE Trans. Signal Processing 62(9):2212–2225.Google Scholar
• Bertsimas D, King A, Mazumder R (2016) Best subset selection via a modern optimization lens. Ann. Statist. 44(2):813–852.Google Scholar
• Candes EJ, Tao T (2005) Decoding by linear programming. IEEE Trans. Inform. Theory 51(12):4203–4215.Google Scholar
• Candes E, Tao T (2007) The Dantzig selector: Statistical estimation when p is much larger than n. Ann. Statist. 35(6):2313–2351.Google Scholar
• Charikar M, Wirth A (2004) Maximizing quadratic programs: Extending Grothendieck’s inequality. 45th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 54–60.Google Scholar
• Chen SS, Donoho DL, Saunders MA (2001) Atomic decomposition by basis pursuit. SIAM Rev. 43(1):129–159.Google Scholar
• Crespo Marques E, Maciel N, Naviner L, Cai H, Yang J (2019) A review of sparse recovery algorithms. IEEE Access 7:1300–1322.Google Scholar
• d’Aspremont A, Ghaoui L, Jordan M, Lanckriet G (2004) A direct formulation for sparse PCA using semidefinite programming. Proc. 18th Internat. Conf. Neural Inform. Processing Systems (MIT Press, Cambridge, MA), 41–48.Google Scholar
• de Klerk E, Vallentin F (2016) On the turing model complexity of interior point methods for semidefinite programming. SIAM J. Optim. 26(3):1944–1961.Google Scholar
• Dettling M (2004) Bagboosting for tumor classification with gene expression data. Bioinformatics 20(18):3583–3593.Google Scholar
• Donato JS, Levinson HW (2022) Structured iterative hard thresholding with on-and off-grid applications. Linear Algebra Its Appl. 638:46–79.Google Scholar
• Dong H, Chen K, Linderoth J (2015) Regularization vs. relaxation: A conic optimization perspective of statistical variable selection. Preprint, submitted October 20, https://arxiv.org/abs/1510.06083.Google Scholar
• Donoho DL (2006) Compressed sensing. IEEE Trans. Inform. Theory 52(4):1289–1306.Google Scholar
• Efron B, Hastie T, Johnstone I, Tibshirani R (2004) Least angle regression. Ann. Statist. 32(2):407–451.Google Scholar
• Flinth A, Kutyniok G (2018) PROMP: A sparse recovery approach to lattice-valued signals. Appl. Comput. Harmonic Anal. 45(3):668–708.Google Scholar
• Gamarnik D, Zadik I (2022) Sparse high-dimensional linear regression. Estimating squared error and a phase transition. Ann. Statist. 50(2):880–903.Google Scholar
• Garey MR, Johnson DS (1990) Computers and Intractability; A Guide to the Theory of NP-Completeness (W. H. Freeman & Co., New York).Google Scholar
• Ge H, Li P (2021) The dantzig selector: Recovery of signal via ℓ1−αℓ2 minimization. Inverse Problems 38(1):015006.Google Scholar
• Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6):1115–1145.Google Scholar
• Grant M, Boyd S (2014) CVX: MATLAB software for disciplined convex programming, version 2.1. Accessed December 1, 2020, https://cvxr.com/cvx/download.Google Scholar
• Grötschel M, Lovász L, Schrijver A (1981) The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2):169–197.Google Scholar
• Gurobi Optimization LLC (2022) Gurobi optimizer reference manual. Accessed December 1, 2022, https://www.gurobi.com.Google Scholar
• Han S, Gómez A, Atamtürk A (2022) The equivalence of optimal perspective formulation and Shor’s SDP for quadratic programs with indicator variables. Oper. Res. Lett. 50(2):195–198.Google Scholar
• Keiper S, Kutyniok G, Lee DG, Pfander GE (2017) Compressed sensing for finite-valued signals. Linear Algebra Its Appl. 532:570–613.Google Scholar
• Kuhn HW, Tucker AW (2014) Nonlinear programming. Giorgi G, Kjeldsen T, eds. Traces and Emergence of Nonlinear Programming (Birkhäuser, Basel, Switzerland), 247–258.Google Scholar
• Laurent M, Rendl F (2005) Semidefinite programming and integer programming. Aardal K, Nemhauser G, Weismantel R, eds. Handbooks in Operations Research and Management Science, vol. 12 (Elsevier, Amsterdam), 393–514.Google Scholar
• Li P, Chen W (2018) Signal recovery under mutual incoherence property and oracle inequalities. Frontiers Math. China 13(6):1369–1396.Google Scholar
• Li Z, Trappe W (2005) Collusion-resistant fingerprints from WBE sequence sets. IEEE Internat. Conf. Comm. 2005 ICC 2005 (Seoul, Korea South), vol. 2, 1336–1340.Google Scholar
• Lounici K (2008) Sup-norm convergence rate and sign concentration property of Lasso and Dantzig estimators. Electronic J. Statist. 2:90–102.Google Scholar
• Ndaoud M, Tsybakov AB (2020) Optimal variable selection and adaptive noisy compressed sensing. IEEE Trans Inform. Theory 66(4):2517–2532.Google Scholar
• Park J, Boyd S (2017) General heuristics for nonconvex quadratically constrained quadratic programming. Preprint, submitted March 22, https://arxiv.org/abs/1703.07870.Google Scholar
• Park J, Boyd S (2018) A semidefinite programming method for integer convex quadratic minimization. Optim. Lett. 12(3):499–518.Google Scholar
• Pilanci M, Wainwright MJ, El Ghaoui L (2015) Sparse learning via Boolean relaxations. Math. Programming 151(1):63–87.Google Scholar
• Prince SJD (2012) Computer Vision: Models, Learning, and Inference, 1st ed. (Cambridge University Press, New York).Google Scholar
• Razeghi B, Voloshynovskiy S, Kostadinov D, Taran O (2017) Privacy preserving identification using sparse approximation with ambiguization. 2017 IEEE Workshop Inform. Forensics Security (WIFS) (IEEE, Piscataway, NJ), 1–6.Google Scholar
• Reeves G, Xu J, Zadik I (2019) The all-or-nothing phenomenon in sparse linear regression. 28th Conf. Learn. Theory (PMLR, New York), 2652–2663.Google Scholar
• Ross Kunz M, She Y (2013) Multivariate calibration maintenance and transfer through robust fused LASSO. J. Chemometrics 27(9):233–242.Google Scholar
• Sasahara H, Hayashi K, Nagahara M (2017) Multiuser detection based on map estimation with sum-of-absolute-values relaxation. IEEE Trans. Signal Processing 65(21):5621–5634.Google Scholar
• Souto NM, Lopes HA (2017) Efficient recovery algorithm for discrete valued sparse signals using an ADMM approach. IEEE Access 5:19562–19569.Google Scholar
• Sparrer S, Fischer RF (2014) Adapting compressed sensing algorithms to discrete sparse signals. WSA 2014 18th Internat. ITG Workshop Smart Antennas (VDE, Frankfurt am Main, Germany), 1–8.Google Scholar
• Sparrer S, Fischer RF (2015) Soft-feedback OMP for the recovery of discrete-valued sparse signals. 2015 23rd Eur. Signal Processing Conf. (EUSIPCO) (IEEE, Piscataway, NJ), 1461–1465.Google Scholar
• Tibshirani R (1996) Regression shrinkage and selection via the Lasso. J. Roy. Statist. Soc. Ser. B Methodological 58(1):267–288.Google Scholar
• Vandenberghe L, Boyd S (1996) Semidefinite programming. SIAM Rev. 38(1):49–95.Google Scholar
• Vershynin R (2018) High-Dimensional Probability: An Introduction with Applications in Data Science, vol. 47 (Cambridge University Press, Cambridge, UK).Google Scholar
• Wainwright MJ (2009) Sharp thresholds for high-dimensional and noisy sparsity recovery using ℓ1-constrained quadratic programming (Lasso). IEEE Trans. Inform. Theory 55(5):2183–2202.Google Scholar
• Yang Z, Wu Y, Zhao W, Zhou Y, Lu Z, Li W, Liao Q (2016) A novel illumination-robust local descriptor based on sparse linear regression. Digital Signal Processing 48:269–275.Google Scholar
• Yardibi T, Li J, Stoica P, Cattafesta LN III (2012) Sparse representations and sphere decoding for array signal processing. Digital Signal Processing 22(2):253–262.Google Scholar
• Yurtsever A, Fercoq O, Cevher V (2019) A conditional-gradient-based augmented Lagrangian framework. Thirty-Sixth Internat. Conf. Machine Learn. (PMLR, New York), 7272–7281.Google Scholar
• Zhao P, Yu B (2006) On model selection consistency of Lasso. J. Machine Learn. Res. 7(90):2541–2563.Google Scholar
• Zhao YB, Li D (2017) A theoretical analysis of sparse recovery stability of Dantzig selector and Lasso. Preprint, submitted November 10, https://arxiv.org/abs/1711.03783.Google Scholar
• Zhu H, Giannakis GB (2011) Exploiting sparse user activity in multiuser detection. IEEE Trans. Comm. 59(2):454–465.Google Scholar