## Low rank matrix approximation **Random Matrices, HSE, 2019** **Denis Zuenko, Sergei Kozlukov** --- ## Problem statement - $A$ be $m\times n$ matrix, $m \leq n$ - Goal: find $B$, $\operatorname{rank}(B)\leq s$, $\|A - B\|\to \min$ - Exact solution: Truncated SVD, $AP_s$ with $P_s$ the projection onto first $s$ singular vectors - Infeasible for large matrices - Approach: Truncated SVD of random submatrix --- ## Algo - Compute row probabilities: $p_i\propto \frac{\|a_i\|^2}{\|A\|_F^2}$ - Sample $k=O(r\log r)$ row indices $I$, with $r$ the stable rank of $A$ - Form matrix $\tilde{A}$ by stacking rows $(\frac{1}{p_i \sqrt{k}} a_i,~i\in I)$ - Compute SVD of $\tilde{A}$ --- ## Error guarantees $$\|A - AP_s\|_2 \leq \sigma_{s+1}(A) + \varepsilon\|A\|_2,$$ $$\|A - AP_s\|_2 \leq 2\varepsilon\|A\|_2$$ --- ## Optimality Sample complexity $s = O(r\log r)$ is optimal --- ## Performance on `np.random.randn(1000, 100)`