A Semidefinite Programming Relaxation for the Sparse Integer Least Squares Problem

In this paper, we study the sparse integer least squares (SILS) problem, an NP-hard variant of least squares with sparse $\{0,\pm 1\}$-vectors. We propose an ${\mathcal{\ell }}_1$-based semidefinite programming (SDP) relaxation and propose a randomized algorithm for SILS, which computes feasible solutions with high probability with an asymptotic approximation ratio $1/T^2$ as long as the sparsity constant $\sigma \ll T$. Our algorithm handles large-scale problems, delivering high-quality approximate solutions for dimensions up to $d=10,000$. The proposed randomized algorithm applies broadly to binary quadratic programs with a cardinality constraint, even for nonconvex objectives. For fixed sparsity, we provide sufficient conditions for our SDP relaxation to solve SILS, meaning that any optimal solution to the SDP relaxation yields an optimal solution to SILS. The class of data input that guarantees that SDP solves SILS is broad enough to cover many cases in real-world applications, such as privacy-preserving identification and multiuser detection. We validate these conditions in two application-specific cases: the feature extraction problem, where our relaxation solves the problem for sub-Gaussian data with weak covariance conditions, and the integer sparse recovery problem, where our relaxation solves the problem in both high- and low-coherence settings under certain conditions.

Funding: A. Del Pia and D. Zhou are partially funded by the Air Force Office of Scientific Research (AFOSR) [Grant FA9550-23-1-0433].

Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoo.2023.0003.