Local Reconstruction of Low-Rank Matrices and Subspaces

摘要

We study the problem of emph{reconstructing a low-rank matrix}, where the input is an n m matrix M over a field F and the goal is to reconstruct a (near-optimal) matrix M that is low-rank and close to M under some distance function . Furthermore, the reconstruction must be local, i.e., provides access to any desired entry of M by reading only a few entries of the input M (ideally, independent of the matrix dimensions n and m ). Our formulation of this problem is inspired by the local reconstruction framework of Saks and Seshadhri (SICOMP, 2010).Our main result is a local reconstruction algorithm for the case where is the normalized Hamming distance (between matrices). Given M that is -close to a matrix of rank d 1 (together with d and ), this algorithm computes with high probability a rank- d matrix M that is O ( d ) -close to M . This is a local algorithm that proceeds in two phases. The emph{preprocessing phase} reads only O ( d 3 ) random entries of M , %runs in time O 1 ( d (8 e ) 2 ln 2 d ) d and stores a small data structure. The emph{query phase} deterministically outputs a desired entry M i j by reading only the data structure and 2 d additional entries of M . % runs in time O ( d 2 ) We also consider local reconstruction in an easier setting, where the algorithm can read an entire matrix column in a single operation. When is the normalized Hamming distance between vectors, we derive an algorithm that runs in polynomial time by applying our main result for matrix reconstruction. For comparison, when is the truncated Euclidean distance and F = R , we analyze sampling algorithms by using statistical learning tools.