论文标题
稀疏整数最小二乘问题的SDP放松
An SDP Relaxation for the Sparse Integer Least Squares Problem
论文作者
论文摘要
在本文中，我们研究\ emph {稀疏整数最小二乘问题}（SILS），这是一种最小二乘的NP-固定变体，具有稀疏的$ \ {0，\ pm 1 \} $ - 矢量。我们提出了一个基于$ \ ell_1 $的SDP放松，以及用于SILS的随机算法，该算法以高概率计算可行的解决方案，只要毫无疑问的近似值$ 1/t^2 $，只要稀疏常数$σ\ ll t $。我们的算法处理大规模的问题，为尺寸提供高质量的近似解决方案，最高$ d = 10,000 $。所提出的随机算法广泛应用于具有基数约束的二进制二次程序，即使对于非凸目标目标也是如此。对于固定的稀疏性，我们为我们的SDP松弛提供了足够的条件来解决SIL，这意味着SDP松弛的任何最佳解决方案均可为SIL提供最佳的解决方案。保证SDP解决SILS的数据输入类别足够广泛，可以涵盖现实世界中的许多情况，例如保留识别和多用户检测的隐私性。我们在两种特定于应用的情况下验证了这些条件：\ emph {特征提取问题}，其中我们的放松解决了具有较弱的协方差条件下的高斯数据的问题，以及\ emph {Integer稀疏恢复问题}，在某些条件下，我们的放松方案在高和低的连贯设置下，我们的放松方面的问题。
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.
