论文标题
立方体上的稀疏近似
Sparse Approximation Over the Cube
论文作者
论文摘要
本文介绍了NP -HARD最小化问题$ \ min \ {\ | b -ax \ | _2：\ x \ in [0,1]^n，| \ text {supp}（x）| \ leqσ\} $，其中$ \ text {supp}（x）= \ {i \ in [n]：x_i \ neq 0 \} $，$σ$是一个正整数。调查的对象是一种自然放松，我们取代$ | \ text {supp}（x）| \ leqσ$ by $ \ sum_i x_i \leqσ$。我们的分析包括何时精确放松的概率观点。我们还从确定性的角度考虑了问题，并在原始问题的最佳解决方案的图像与$ a $下的放松之间的距离之间提供了界限。这导致了通用矩阵$ a \ in \ mathbb {z}^{m \ times n} $的算法，并实现了多项式运行时间，只要$ m $和$ \ | a \ | _ {\ | _ {\ iffty} $已固定。
This paper presents an anlysis of the NP-hard minimization problem $\min \{\|b - Ax\|_2: \ x \in [0,1]^n, | \text{supp}(x) | \leq σ\}$, where $\text{supp}(x) = \{i \in [n]: x_i \neq 0\}$ and $σ$ is a positive integer. The object of investigation is a natural relaxation where we replace $| \text{supp}(x) | \leq σ$ by $\sum_i x_i \leq σ$. Our analysis includes a probabilistic view on when the relaxation is exact. We also consider the problem from a deterministic point of view and provide a bound on the distance between the images of optimal solutions of the original problem and its relaxation under $A$. This leads to an algorithm for generic matrices $A \in \mathbb{Z}^{m \times n}$ and achieves a polynomial running time provided that $m$ and $\|A\|_{\infty}$ are fixed.
