Testing Sparsity over Known and Unknown Bases
Testing Sparsity over Known and Unknown Bases
复制标题
测试已知和未知碱基的稀疏性
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Suprovat Ghoshal
中科院分区：
文献类型：
--
作者：
Siddharth Barman;Arnab Bhattacharyya;Suprovat Ghoshal
稀疏性是真实的向量的一个基本属性，在各种各样的应用中被利用。在这项工作中，我们描述了属性测试算法的稀疏性，观察输入的低维投影。
我们考虑两种设置。在第一种设置中，对于R^{d x m}中的给定设计矩阵A，我们测试R^d中的输入向量y是否等于某个k稀疏单位向量x的Ax。我们的算法将输入投影到O（k \eps^{-2} log m）维上，如果属性成立则接受，如果属性成立则拒绝。||y轴||> \eps对于任何O（k/\eps^2）-稀疏向量x，并且在m中以时间多项式运行。我们的算法是基于近似Caratheodory定理。以前已知的算法，解决问题的任意A与定性相似的保证运行在指数时间。
在第二设置中，设计矩阵A是未知的。给定输入向量y_1，y_2，.，y_p在R^d中，其作为列的级联形成R^{d x p}中的Y，目标是决定对于R^{d x m}中的矩阵A和R^{m x p}中的矩阵X，Y是否=AX，使得X的每一列是k-稀疏的，或者Y是否“远离”具有这样的分解。我们给出了这样一个测试算法，它将输入向量投影到O（log p/\eps^2）维，并假设未知数A满足k-限制等距。我们的分析给出了一个新的强大的高斯宽度的稀疏性方面的表征。
Sparsity is a basic property of real vectors that is exploited in a wide variety of applications. In this work, we describe property testing algorithms for sparsity that observe a low-dimensional projection of the input.
We consider two settings. In the first setting, for a given design matrix A in R^{d x m}, we test whether an input vector y in R^d equals Ax for some k-sparse unit vector x. Our algorithm projects the input onto O(k \eps^{-2} log m) dimensions, accepts if the property holds, rejects if ||y - Ax|| > \eps for any O(k/\eps^2)-sparse vector x, and runs in time polynomial in m. Our algorithm is based on the approximate Caratheodory's theorem. Previously known algorithms that solve the problem for arbitrary A with qualitatively similar guarantees run in exponential time.
In the second setting, the design matrix A is unknown. Given input vectors y_1, y_2,...,y_p in R^d whose concatenation as columns forms Y in R^{d x p} , the goal is to decide whether Y=AX for matrices A in R^{d x m} and X in R^{m x p} such that each column of X is k-sparse, or whether Y is "far" from having such a decomposition. We give such a testing algorithm which projects the input vectors to O(log p/\eps^2) dimensions and assumes that the unknown A satisfies k-restricted isometry. Our analysis gives a new robust characterization of gaussian width in terms of sparsity.
DOI：
10.1145/3302249
发表时间：
2015-07
期刊：
ACM Transactions on Algorithms (TALG)
影响因子：
--
作者：
Avrim Blum;Sariel Har-Peled;Benjamin Raichel
通讯作者：
Avrim Blum;Sariel Har-Peled;Benjamin Raichel