2014 ImprovedTestingofLowRankMatrice

• (Li et al., 2014) ⇒ Yi Li, Zhengyu Wang, and David P. Woodruff. (2014). “Improved Testing of Low Rank Matrices.” In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2014) Journal. ISBN:978-1-4503-2956-9 doi:10.1145/2623330.2623736

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222014%22+Improved+Testing+of+Low+Rank+Matrices
• http://dl.acm.org/citation.cfm?id=2623330.2623736&preflayout=flat#citedby

Quotes

Author Keywords

• Algorithm design and analysis; computations on matrices; dimensionality reduction; principal component analysis; property testing; robustness; stable rank

Abstract

We study the problem of determining if an input matrix A ε R ^{m x n} can be well-approximated by a low rank matrix. Specifically, we study the problem of quickly estimating the rank or stable rank of A, the latter often providing a more robust measure of the rank. Since we seek significantly sublinear time algorithms, we cast these problems in the property testing framework. In this framework, A either has low rank or stable rank, or is far from having this property . The algorithm should read only a small number of entries or rows of A and decide which case A is in with high probability. If neither case occurs, the output is allowed to be arbitrary. We consider two notions of being far: (1) A requires changing at least an ε-fraction of its entries, or (2) A requires changing at least an ε-fraction of its rows. We call the former the. (2003). “entry Model” and the latter the “row model”. We show:

• For testing if a matrix has rank at most d in the entry model, we improve the previous number of entries of A that need to be read from O(d2/ε2) (Krauthgamer and Sasson, SODA 2003) to O(d2/ε). Our algorithm is the first to adaptively query the entries of A, which for constant d we show is necessary to achieve O(1/ε) queries. For the important case of d = 1 we also give a new non-adaptive algorithm, improving the previous O(1/ε2) queries to O(log2(1/ε) / ε).
• For testing if a matrix has rank at most d in the row model, we prove an Ω(d/ε) lower bound on the number of rows that need to be read, even for adaptive algorithms. Our lower bound matches a non-adaptive upper bound of Krauthgamer and Sasson.
• For testing if a matrix has stable rank at most d in the row model or requires changing an ε/d-fraction of its rows in order to have stable rank at most d, we prove that reading θ(d/ε2) rows is necessary and sufficient.

We also give an empirical evaluation of our rank and stable rank algorithms on real and synthetic datasets.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2014 ImprovedTestingofLowRankMatrice	Yi Li Zhengyu Wang David P. Woodruff			Improved Testing of Low Rank Matrices				10.1145/2623330.2623736		2014