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.

  • $\begingroup$ Do you know about the "singular value decomposition"? $\endgroup$ – kimchi lover Dec 13 '17 at 0:14
  • $\begingroup$ 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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.