This is the authors' abstract. We don't add key points for this paper.
In several applications, the data consists of an m/spl times/n matrix A and it is of interest to find an approximation D of a specified rank k to A where, k is much smaller than m and n. Traditional methods like the Singular Value Decomposition (SVD) help us find the "best" such approximation. However, these methods take time polynomial in m, n which is often too prohibitive. In this paper, we develop an algorithm which is qualitatively faster provided we may sample the entries of the matrix according to a natural probability distribution. Indeed, in the applications such sampling is possible. Our main result is that we can find the description of a matrix D* of rank at most k so that /spl par/A-D*/spl par//sub F//spl les/min/D,rank(D)/spl les/k/spl par/A-D/spl par//sub F/+/spl epsiv//spl par/A/spl par//sub F/ holds with probability at least 1-/spl delta/. (For any matrix M, /spl par/M/spl par//sub F//sup 2/ denotes the sum of the squares of all the entries of M.) The algorithm takes time polynomial in k, 1//spl epsiv/, log(1//spl delta/) only, independent of m, n.
Answers are grounded in this paper and cite their sources.
No takes yet. Share an insight, caveat, or question.
Frieze et al. (2002) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: