Testing matrix rank, optimally

DOI10.1137/1.9781611975482.46MaRDI QIDQ5236228zbMATH OpenOpenAlexFDO

Authors Maria-Florina Balcan, Yi Li, David P. Woodruff, Hongyang Zhang

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.08171

Mathematics Subject Classification ID

Vector spaces, linear dependence, rank, lineability (15A03) Randomized algorithms (68W20)

Abstract: We show that for the problem of testing if a matrix $Ain{F}^{nimesn}$ has rank at most $d$, or requires changing an $epsilon$-fraction of entries to have rank at most $d$, there is a non-adaptive query algorithm making $widetildeO(d^2/epsilon)$ queries. Our algorithm works for any field $F$. This improves upon the previous $O(d^2/epsilo{n}^2)$ bound (SODA'03), and bypasses an $Omega(d^2/epsilo{n}^2)$ lower bound of (KDD'14) which holds if the algorithm is required to read a submatrix. Our algorithm is the first such algorithm which does not read a submatrix, and instead reads a carefully selected non-adaptive pattern of entries in rows and columns of $A$. We complement our algorithm with a matching query complexity lower bound for non-adaptive testers over any field. We also give tight bounds of $widetildeTheta(d^2)$ queries in the sensing model for which query access comes in the form of $langle{X}_i,Aangle:=tr(X_i^{o}pA)$; perhaps surprisingly these bounds do not depend on $epsilon$. We next develop a novel property testing framework for testing numerical properties of a real-valued matrix $A$ more generally, which includes the stable rank, Schatten-$p$ norms, and SVD entropy. Specifically, we propose a bounded entry model, where $A$ is required to have entries bounded by $1$ in absolute value. We give upper and lower bounds for a wide range of problems in this model, and discuss connections to the sensing model above.

Recommendations

• Property testing of the Boolean and binary rank
• Adaptive Sampling and Fast Low-Rank Matrix Approximation
• Fast monte-carlo algorithms for finding low-rank approximations
• Sampling from large matrices
• Local reconstruction of low-rank matrices and subspaces

Cited in

(9)

• Testing proximity to subspaces: approximate \(\ell_\infty\) minimization in constant time
• Testing matrix function algorithms using identities
• Integer matrix rank certification
• Querying a Matrix through Matrix-Vector Products
• Querying a Matrix Through Matrix-Vector Products.
• Non-convex matrix completion and related problems via strong duality
• Optimal eigenvalue approximation via sketching
• Optimal estimation of Schatten norms of a rectangular matrix
• Property testing of the Boolean and binary rank

This page was built for publication: Testing matrix rank, optimally

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236228)