
Upload Video
videos in mp4/mov/flv
close
Upload video
Note: publisher must agree to add uploaded document 
Upload Slides
slides or other attachment
close
Upload Slides
Note: publisher must agree to add uploaded document 
Feedback
help us improve
close
Feedback
Please help us improve your experience by sending us a comment, question or concern
Description
Our first algorithm for volume sampling $k$subsets of rows from an $m$by$n$ matrix runs in $O(kmn^omega log n)$ arithmetic operations and a second variant of it for $(1+epsilon)$approximate volume sampling runs in $O(mn log m cdot k^{2}/epsilon^{2} + m log^{omega} m cdot k^{2omega+1}/epsilon^{2omega} cdot log(k epsilon^{1} log m))$ arithmetic operations, which is almost linear in the size of the input (i.e., the number of entries) for small $k$.
Our efficient volume sampling algorithms imply the following results for lowrank matrix approximation: egin{enumerate} item Given $A in R^{m imes n}$, in $O(kmn^{omega} log n)$ arithmetic operations we can find $k$ of its rows such that projecting onto their span gives a $sqrt{k+1}$approximation to the matrix of rank $k$ closest to $A$ under the Frobenius norm. This improves the $O(k sqrt{log k})$approximation of Boutsidis, Drineas and Mahoney cite{BDM} and matches the lower bound shown in cite{DRVW}. The method of conditional expectations gives a emph{deterministic} algorithm with the same complexity. The running time can be improved to $O(mn log m cdot k^{2}/epsilon^{2} + m log^{omega} m cdot k^{2omega+1}/epsilon^{2omega} cdot log(k epsilon^{1} log m))$ at the cost of losing an extra $(1+epsilon)$ in the approximation factor. item The same rows and projection as in the previous point give a $sqrt{(k+1)(nk)}$approximation to the matrix of rank $k$ closest to $A$ under the spectral norm. In this paper, we show an almost matching lower bound of