An SDP Relaxation for the Sparse Integer Least Squares Problem
For researchers in optimization and signal processing, this work provides a theoretically grounded SDP relaxation that can solve a hard combinatorial problem under realistic data conditions, though the practical impact depends on the strictness of the conditions.
The paper proposes an ℓ1-based SDP relaxation and a randomized algorithm for the NP-hard sparse integer least squares problem, achieving an asymptotic approximation ratio of 1/T² for sparsity σ ≪ T and handling dimensions up to 10,000. The relaxation provably solves the problem under broad conditions applicable to real-world tasks like privacy-preserving identification and multiuser detection.
In this paper, we study the \emph{sparse integer least squares problem} (SILS), an NP-hard variant of least squares with sparse $\{0, \pm 1\}$-vectors. We propose an $\ell_1$-based SDP relaxation, and 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 $σ\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 non-convex 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 which 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 \emph{feature extraction problem}, where our relaxation solves the problem for sub-Gaussian data with weak covariance conditions, and the \emph{integer sparse recovery problem}, where our relaxation solves the problem in both high and low coherence settings under certain conditions.