Low rank approximation and regression in input sparsity time 论文
2013引用 395
Sparse and Compressive Sensing TechniquesStochastic Gradient Optimization TechniquesTensor decomposition and applications
详细信息
- 发表日期
- 2013-05-28
- 发表年份
- 2013
关键词
Sparse and Compressive Sensing TechniquesStochastic Gradient Optimization TechniquesTensor decomposition and applications
摘要
We design a new distribution over poly(r ε-1) x n matrices S so that for any fixed n x d matrix A of rank r, with probability at least 9/10, SAx2 = (1 pm ε)Ax2 simultaneously for all x ∈ Rd. Such a matrix S is called a subspace embedding. Furthermore, SA can be computed in O(nnz(A)) + ~O(r2ε-2) time, where nnz(A) is the number of non-zero entries of A. This improves over all previous subspace embeddings, which required at least Ω(nd log d) time to achieve this property. We call our matrices S sparse embedding matrices.