Sparse Approximation via Generating Point Sets
Sparse Approximation via Generating Point Sets
复制标题
DOI：
10.1145/3302249
复制
发表时间：
2015-07
期刊：
影响因子：
--
通讯作者：
Avrim Blum;Sariel Har-Peled;Benjamin Raichel
中科院分区：
文献类型：
--
作者：
Avrim Blum;Sariel Har-Peled;Benjamin Raichel
对于单位球B ∈ Rd中的n个点的集合P，考虑寻找一个小子集T ∈ P使得其凸包ε-逼近原始集合的凸包的问题。具体地，T的凸船体与P的凸船体之间的Hausdorff距离应该至多为ε。我们提出了一个有效的算法来计算这样的ε′-近似的大小kalg，其中ε ′是ε的函数，kalg是这样的ε-近似的最小大小kopt的函数。令人惊讶的是，在两个边界中都不依赖于维度d。此外，P中的每个点都可以用T中的点的凸组合来ε-近似，其是O（1/ε2）-稀疏的。我们的结果可以被看作是一种稀疏的，凸的自动编码方法：近似表示数据在一个紧凑的方式使用稀疏组合的一个小子集T的原始数据。新算法可以核化，并且保持了原始输入的稀疏性。
For a set P of n points in the unit ball b⊆ Rd, consider the problem of finding a small subset T⊆ P such that its convex-hull ε-approximates the convex-hull of the original set. Specifically, the Hausdorff distance between the convex hull of T and the convex hull of P should be at most ε. We present an efficient algorithm to compute such an ε′-approximation of size kalg, where ε ′ is a function of ε and kalg is a function of the minimum size kopt of such an ε-approximation. Surprisingly, there is no dependence on the dimension d in either of the bounds. Furthermore, every point of P can be ε-approximated by a convex-combination of points of T that is O(1/ε2)-sparse. Our result can be viewed as a method for sparse, convex autoencoding: approximately representing the data in a compact way using sparse combinations of a small subset T of the original data. The new algorithm can be kernelized, and it preserves sparsity in the original input.