Low Rank Representation

1. Matrix Norm and Singular Value

(1). nuclear norm: $||X||_* = ||\text{singular values}||_1$

(2). frobenius norm: $||X||_F =\sqrt{\sum_{i,j}X_{i,j}^2} = ||\text{singular values}||_2$

(3). spectral norm: $||X||_2 = sup_v{ \frac{||Xv||_2}{||v||_2}}=|| \text{singular values}||_{inf}$

(1-norm and inf-norm are a pair of dual norms.)

2. Low-Rank problem

($||E||_{2,1}$ is the sum of all column vectors' 2-norm)

$Z \in \mathbb{R}^{d*n}$ contains n data points coming from several subspaces, d is the data dimension. For example, $X \in \mathbb{R}^{1000*50}$ contains 50 images of 5 people, each image has 1000 pixels.

In the face example, since there are only 5 people in 50 images, the "rank" of the data matrix is 5, so we want to transform the data matrix to low-rank representation.

Suppose $A$ is a 'dictionary' that linearly spans the data space, $Z$ is a coefficient matrix, and $X$ is obtained by noisy observation $AZ+E$ where $E$ is the error term.

Since minimizing the rank of $Z$ is np-hard, we can relax the problem by replacing $rank(Z)$ with $||X||_*$. Since $||X||_* = ||\text{singular values}||_1$ and 1-norm minimization leads to sparsity, sparsity in singular values yields low rank. We can approximately solve the original optimization problem by solving

3. Singular Value Shrinkage

Consider the regularized frobenius norm minimization problem

$f(x)$ is a non-differentiable function, when $\vec{0} \in \frac{\partial f}{\partial x}$, $f$ achieves its minimum where $\frac{\partial f}{\partial x}$ is the subdifferential of $f$.

We apply singular value decomposition to $Y$

where $diag(\Sigma_0)>\tau$, $diag(\Sigma_0)<=\tau$.

Define singular value shrink operator as

Perform singular value shrinkage on $Y$

The subgradient of nuclear norm is defined by

Let $U = U_0, V = V_0, W = \frac{1}{\tau}U_1 \Sigma_1 V_1^T$, $Y-D_{\tau}(Y) \in \tau \partial ||X||_*$.

Let $X = D_{\tau}(Y)$, $X - Y + Y - D_{\tau}(Y) =0 \in \frac{\partial f}{\partial x}$. So $X = D_{\tau}(Y)$ minimizes $\frac{1}{2}||X-Y||_F^2 + \tau ||X||_*$

4. Augmented Lagrangian Multiplier

Define the augmented lagrangian as

The optimality condition for the original problem is

1.$h_i(x^*) = 0$

2.$\nabla_xL(x^*, v^*) = \nabla f(x^*) + \sum_i v_i \nabla h_i(x^*) = 0$

if $x^*, v^*$ is the optimal of the original problem, then

$x^*, v^*$ also minimizes the augmented lagrangian.

When we solve the original problem with augmented lagangian, we want to minimize the augmented lagrangian and keep $\nabla_xA(x,v,c) = \nabla_xL(x,v)$

To keep $\nabla_x A(x',v,c) = \nabla L(x',v')$, set $v_i' = v_i + c*h_i(x')$

The augmented lagrangian algorithm

repeat until convergence{
    x' = argmin_x L(x,v)
    v_i' = v_i + c * h_i(x')
    x = x'
    v = v'
}

5. Solve Low-Rank Problem

The low-rank representation problem

Transform is to the equivalent problem

Form the lagrangian and the augmented lagrangian

• Update $J$ (Step 1 in augmented lagrangian )

Apply SVD on $Z + \frac{1}{c}Y_2$

where $diag(\Sigma_0) > 1/c$, $diag(\Sigma_1) <= 1/c$.

Perform singular value shrinkage with threshold $1/c$ on $Z + \frac{1}{c}Y_2$

Since $\partial ||X||_* = \{UV^T + W | U^TW=0, WV=0, ||W||_2<=1\}$, let $U=U_0, V=V_0, W=c * U_1 \Sigma_1V_1^T$.

$J^* = (Z + \frac{1}{c}Y_2) - \frac{1}{c} \partial||J||_* = D_{1/c}(Z + \frac{1}{c}Y_2)$

• Update $Z$ (Step 1 in augmented lagrangian )

• Update E (Step 1 in augmented lagrangian )

This solution can be found here.

• Update dual variable $Y_1$ and $Y_2$

6. Low-Rank Representation on Face Image Recovery

Suppose we have m images of n people (n< m), some of which are heavily corrupted. Want to recover these images by low-rank representation.

In this example, we use the dataset itself as the dictionary (i.e. $A=X$), thus the optimization problem reduce to

Here are some results