# Find $\vec{u}$ and $\vec v$ such that $\vec u \vec v^T$ most closely approximates A?

Given an $m \times n$ matrix A, how can you solve for two vectors $\vec u$ and $\vec v$ such that

$$\sum_{i,j} (u_i v_j-A_ij)^2$$

is minimized? There's a pretty simple recursive formula where:

$\vec u_0 = [1,1,,1,...1]^T,\; \vec v_0=[1,1, 1, ...1]^T$ and $$u_{n+1}=\frac{A \vec v_n}{\langle \vec v_n,.\vec v_n\rangle} \;\text{and}\; v_{n+1}=\frac{A^T \vec u_{n+1}}{\langle \vec u_{n+1}, \vec u_{n+1}\rangle}$$

That converges pretty quickly, but I'm hoping for an exact solution.

• Do you know about the "singular value decomposition"? – kimchi lover Dec 13 '17 at 0:14
• That iterative scheme is just a variant of the power method. How quickly it converges depends on how far is the largest singular value from the rest. – Algebraic Pavel Dec 13 '17 at 0:27

The best rank one approximation to $A$ is $\sigma_1 uv^\top$ where $u$ and $v$ are the top left singular vector and top right singular vector respectively, and $\sigma_1$ is the top singular value of $A$ (a.k.a. the operator norm of $A$). Specifically, if $A=U\Sigma V^\top$ is the SVD of $A$ with $\Sigma$ having diagonal elements $\sigma_1 \ge \sigma_2 \ge \cdots$ in decreasing order, then $u$ and $v$ are the first columns of $U$ and $V$ respectively.

Note also that your original problem has a misspecification issue. For example, if $u$ and $v$ minimize your objective function, then so do $2u$ and $v/2$.

Even taking into account this misspecification issue, the solution will not be unique in the case where more than one singular value is the top singular value.