Matrix approximation

Approximating a matrix

The problem

Take set of matrices S. Want ${\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}_{B\in S}\parallel A-B\parallel$ is minimized wrt some $\parallel \parallel$ and some set S.

The error metric

Also, often $\parallel .\parallel$ is an operator norm, as this ensures that $\parallel (A-B)x\parallel$ is low wrt the corresponding vector norm. Other times, as in the case of matrix completion problems, it may be desirable for $\parallel \parallel$ to be the Frobenius norm.

Low rank (k) factorization problem

In many problems, S is the set of rank k matrices, where k is small.

Often, we prefer $A\approx B=X{Y}^T$ rather than computing B, where rank(X), rank(Y) $\le k$: $A$ may be sparse, but the best B may be dense, so we may run out of memory while storing, and out of time while computing Bx. You can always get $B=X{Y}^T$ from B just by taking SVD of B.

Restriction to subspace view

Similarly, may want restriction of $A$ to a low rank subspace: $B=Q{Q}^{T}A$, Q is low rank, orthogonal; but it should be the best subspace which minimizes the error. $A$ good Q tries to approximate the range space of A.

Sparse approximation

Maybe want \(\min_B \norm{B-A}_2: \norm{B}0 \leq k\). This can be solved just by setting B = $A$, and then dropping the k smallest \(B{i, j}\) from B.

1 norm regularized form

Even the optimization problem \(\min_B \norm{B-A}_2^{2} + l\norm{B(:)}1 \) leads to sparse solutions. This form is useful in some sparse matrix completion ideas. Solution: just take B=A, and then drom \(B{i,j} \leq l/2\): (thresholding!)

Pf: $\underset{B}{min}\sum _{i,j}(B_{i,j}-A_{i,j}{)}^2+l\sum _{i,j}sgn(B_{i,j})B_{i,j}$. Let B’ be the solution to this. If $A_{i,j}\ge 0$, so is $B_{i,j}$; If $A_{i,j}\le 0$, so is $B_{i,j}$: if they oppose in sign, setting $B_{i,j}=0$ definitely lowers the objective. So, get equivalent problem: $\underset{B}{min}\sum _{i,j}(B_{i,j}-A_{i,j}{)}^2+l\sum _{i,j}sgn(A_{i,j})B_{i,j}$ subject to $sgn(A)=sgn(B)$. The new objective is differentiable. Its optimality condition: $B_{i,j}=A_{i,j}-l/2$; but the feasible set only includes $sgn(B)=sgn(A)$. So if $A_{i,j}-l/2\le 0$, the feasible B closest to the minimum of $\underset{B}{min}\sum _{i,j}(B_{i,j}-A_{i,j}{)}^2+l\sum _{i,j}sgn(A_{i,j})B_{i,j}$ has the corresponding $B_{i,j}=0$.

Best rank t approximation of A from SVD

The approximation

Let $A_t=\sum _{j=1}^t{\mathrm{\Sigma }}_j{u}_j{v}_j^{\ast }$ be the approximation. $A_t$ is the best rank t approx to $A$ (wrt \(\norm{.}{2}\), \(\norm{.}{F}\)), captures max energy of $A$ possible: $\parallel A-A_t\parallel =\underset{B}{inf}\parallel A-B\parallel$.

Approximation error

Then, approximation error is $A-A_t=\sum _{i=t+1}^r{\sigma }_i{u}_i{v}_i^{\ast }$. As $\parallel X\parallel ={\sigma }_1(X)$: \(\norm{A-A_{t}}{2} = \sw{t+1}\), \(\norm{A-A_{t}}{F} = \sqrt{\sum{i=t+1}^{r} \sw_{i}^{2}}\).

Geometric interpretation

Approximate hyperellipse by line, 2-dim ellipse etc…

Approximating domain and range spaces

Using SVD for example, $A$ can be viewed as a combination of rotation and diagonal matrices. So, getting a low rank approximation of $A$ can be viewed as first getting low rank approximations of the range and domain spaces with orthogonal basis matrices $U_t$ and $V_t$ respectively, and then finding a square $S=U_t^{T}A{V}_t^T$ such that $A\approx U_{t}S{V}_t$.

Proof

Proof by $\Rightarrow \Leftarrow$: dim(N(B))= r-t, Let $\mathrm{\forall }w\in N(B),\parallel Aw\parallel =\parallel (A-B)w\parallel <{\mathrm{\Sigma }}_{t+1}\parallel w\parallel$; but $\mathrm{\exists }$ t+1 subspace $\{v:\parallel Av\parallel \ge {\mathrm{\Sigma }}_{t+1}\}$; $dim(\left\{w\right\})+\dim (\left\{v\right\})=r+1$: absurd.

So, $$\sw_{k} = \min_{S \subset C^{n}, dim(S) = n-k+1} \max_{x \in S} \norm{Ax}{2} \ = \max{S \subset C^{n}, dim(S) = k} \min_{x \in S} \norm{Ax}_{2}$$.

Randomized Approach

Take the $A\approx B=Q{Q}^{T}A$ view. $A$ good Q must span $U_k$. Can use something akin to the power method of finding ev. Take random m*k matrix W. $Y=(A{A}^T{)}^{q}AW=U{\mathrm{\Sigma }}^{q+1}VW$, and get $Y=QR$ to get Q. q = 4 or 5 is sufficient to get good approximation of $U_k$. (Tropp etal) if you aim to get k+p approximation, you get low expected error.

With few observations in A only

Same as the missing value estimation problem.

Missing value estimation

The problem

May be you have the matrix $A$, and you have observed only a few entries $O$. If there were no other conditions, there would be infinite solutions. But, maybe you also know that $A$ has some special structure: low rank, or block structure or smoothness etc..

Can also view as getting an approximation $B\in S$ for $A$, where S is the set of matrices having the specified structure.

Smoothness constraint

Sovle $min\sum _{i,j}d(B_{i,j},B_{i-1,j})+d(B_{i,j},B_{i,j-1})$ such that $B_{i,j}=A_{i,j}\mathrm{\forall }(i,j)\in O$. If we use l2 or l1 metrics for d(), this can be solved with convex optimization.

Low rank constraint

$rank(B)\le k$: this is not a convex constraint.

Singular value projection (SVP)

(Jain, Meka, Dhillon) Set \(B^{(0)}{i,j} = A{i,j} \forall (i,j) \in O\), set remaining values in $B^{(0)}$ arbitrarily. Then, in iteration i, do SVD of $B^{(i)}$ to get rank k approximation $B^{(i+1)}$, set \(B^{(i+1)}{i,j} = A{i,j} \forall (i,j) \in O\).

Projection viewpoint

Take $$S_1=\{B:B_{i,j}=A_{i,j}\mathrm{\forall }(i,j)\in O\},S_2=\{B:rank(B)\le k\}\text{(}.Youstartwith\text{)}{B}_0\in S_1\text{(},projectittotheclosest\text{)}C\in S_2\text{(},projectCtotheclosest\text{)}{B}_1\in S_1$$ etc..

Applications

The netflix problem.