Low rank approximation - Alchetron, The Free Social Encyclopedia

In mathematics, low-rank approximation is a minimization problem, in which the cost function measures the fit between a given matrix (the data) and an approximating matrix (the optimization variable), subject to a constraint that the approximating matrix has reduced rank. The problem is used for mathematical modeling and data compression. The rank constraint is related to a constraint on the complexity of a model that fits the data. In applications, often there are other constraints on the approximating matrix apart from the rank constraint, e.g., non-negativity and Hankel structure.

Definition

Given

structure specification S : R n p → R m × n ,

vector of structure parameters p ∈ R n p ,

norm ∥ ⋅ ∥ , and

desired rank r ,

minimize over p ^ ∥ p − p ^ ∥ subject to rank ⁡ ( S ( p ^ ) ) ≤ r .

Applications

Linear system identification, in which case the approximating matrix is Hankel structured.

Machine learning, in which case the approximating matrix is nonlinearly structured.

Recommender system, in which case the data matrix has missing values and the approximation is categorical.

Distance matrix completion, in which case there is a positive definiteness constraint.

Natural language processing, in which case the approximation is nonnegative.

Computer algebra, in which case the approximation is Sylvester structured.

Basic low-rank approximation problem

The unstructured problem with fit measured by the Frobenius norm, i.e.,

minimize over D ^ ∥ D − D ^ ∥ F subject to rank ⁡ ( D ^ ) ≤ r

has analytic solution in terms of the singular value decomposition of the data matrix. The result is referred to as the matrix approximation lemma or Eckart–Young–Mirsky theorem. Let

D = U Σ V ⊤ ∈ R m × n , m ≤ n

be the singular value decomposition of D and partition U , Σ =: diag ⁡ ( σ 1 , … , σ m ) , and V as follows:

U =: [ U 1 U 2 ] , Σ =: [ Σ 1 0 0 Σ 2 ] , and V =: [ V 1 V 2 ] ,

where Σ 1 is r × r , U 1 is m × r , and V 1 is n × r . Then the rank- r matrix, obtained from the truncated singular value decomposition

D ^ ∗ = U 1 Σ 1 V 1 ⊤ ,

is such that

∥ D − D ^ ∗ ∥ F = min rank ⁡ ( D ^ ) ≤ r ∥ D − D ^ ∥ F = σ r + 1 2 + ⋯ + σ m 2 .

The minimizer D ^ ∗ is unique if and only if σ r + 1 ≠ σ r .

Proof of Eckart–Young–Mirsky theorem (for spectral norm)

Let A ∈ R m × n be a real (possibly rectangular) matrix with m ≥ n . Suppose that

A = U Σ V ⊤

is the singular value decomposition of A . Recall that U and V are orthogonal matrices, and Σ is an m × n diagonal matrix with entries ( σ 1 , σ 2 , ⋯ , σ n ) such that σ 1 ≥ σ 2 ≥ ⋯ ≥ σ n ≥ 0 .

We claim that the best rank k approximation to A in the spectral norm, denoted by ∥ ⋅ ∥ 2 , is given by

A k = ∑ i = 1 k σ i u i v i ⊤

where u i and v i denote the i th column of U and V , respectively.

First, note that we have

∥ A − A k ∥ 2 = ∥ ∑ i = k + 1 n σ i u i v i ⊤ ∥ 2 = σ k + 1

Therefore, we need to show that if B k = X Y ⊤ where X and Y have k columns then ∥ A − A k ∥ 2 = σ k + 1 ≤ ∥ A − B k ∥ 2 .

Since Y has k columns, then there must be a linear combination of the first k + 1 columns of V , i.e.,

w = γ 1 v 1 + ⋯ + γ k + 1 v k + 1 ,

such that Y ⊤ w = 0 . Without loss of generality, we can scale w so that ∥ w ∥ 2 = 1 or (equivalently) γ 1 2 + ⋯ + γ k + 1 2 = 1 . Therefore,

∥ A − B k ∥ 2 2 ≥ ∥ ( A − B k ) w ∥ 2 2 = ∥ A w ∥ 2 2 = γ 1 2 σ 1 2 + ⋯ + γ k + 1 2 σ k + 1 2 ≥ σ k + 1 2 .

The result follows by taking the square root of both sides of the above inequality.

Proof of Eckart–Young–Mirsky theorem (for Frobenius norm)

Let A ∈ R m × n be a real (possibly rectangular) matrix with m ≥ n . Suppose that

A = U Σ V ⊤

is the singular value decomposition of A .

We claim that the best rank k approximation to A in the Frobenius norm, denoted by ∥ ⋅ ∥ F , is given by

A k = ∑ i = 1 k σ i u i v i ⊤

where u i and v i denote the i th column of U and V , respectively.

First, note that we have

∥ A − A k ∥ F 2 = ∥ ∑ i = k + 1 n σ i u i v i ⊤ ∥ F 2 = ∑ i = k + 1 n σ i 2

Therefore, we need to show that if B k = X Y ⊤ where X and Y have k columns then ∥ A − A k ∥ F 2 = ∑ i = k + 1 n σ i 2 ≤ ∥ A − B k ∥ F 2 .

By the triangle inequality with the spectral norm, if A = A ′ + A ″ then σ 1 ( A ) ≤ σ 1 ( A ′ ) + σ 1 ( A ″ ) . Suppose A k ′ and A k ″ denote the best rank k approximation to A ′ and A ″ , respectively. Then, for any i , j ≥ 1

σ i ( A ′ ) + σ j ( A ″ ) = σ 1 ( A ′ − A i − 1 ′ ) + σ 1 ( A ″ − A j − 1 ″ ) ≥ σ 1 ( A − A i − 1 ′ − A j − 1 ″ ) ≥ σ i + j − 1 ( A ) .

Since σ k + 1 ( B k ) = 0 , when A ′ = A − B k and A ″ = B k we conclude that for i ≥ 1

σ i ( A − B k ) ≥ σ k + i ( A ) .

Therefore,

∥ A − B k ∥ F 2 = ∑ i = 1 n σ i ( A − B k ) 2 ≥ ∑ i = k + 1 n σ i ( A ) 2 = ∥ A − A k ∥ F 2 ,

as required.

Weighted low-rank approximation problems

The Frobenius norm weights uniformly all elements of the approximation error D − D ^ . Prior knowledge about distribution of the errors can be taken into account by considering the weighted low-rank approximation problem

minimize over D ^ vec ⊤ ⁡ ( D − D ^ ) W vec ⁡ ( D − D ^ ) subject to rank ⁡ ( D ^ ) ≤ r ,

where v e c ( A ) vectorizes the matrix A column wise and W is a given positive (semi)definite weight matrix.

The general weighted low-rank approximation problem does not admit an analytic solution in terms of the singular value decomposition and is solved by local optimization methods, which provide no guarantee that a globally optimal solution is found.

Image and kernel representations of the rank constraints

Using the equivalences

rank ⁡ ( D ^ ) ≤ r ⟺ there are P ∈ R m × r and L ∈ R r × n such that D ^ = P L

and

rank ⁡ ( D ^ ) ≤ r ⟺ there is full row rank R ∈ R m − r × m such that R D ^ = 0

the weighted low-rank approximation problem becomes equivalent to the parameter optimization problems

minimize over D ^ , P and L vec ⊤ ⁡ ( D − D ^ ) W vec ⁡ ( D − D ^ ) subject to D ^ = P L

and

minimize over D ^ and R vec ⊤ ⁡ ( D − D ^ ) W vec ⁡ ( D − D ^ ) subject to R D ^ = 0 and R R ⊤ = I r ,

where I r is the identity matrix of size r .

Alternating projections algorithm

The image representation of the rank constraint suggests a parameter optimization methods, in which the cost function is minimized alternatively over one of the variables ( P or L ) with the other one fixed. Although simultaneous minimization over both P and L is a difficult biconvex optimization problem, minimization over one of the variables alone is a linear least squares problem and can be solved globally and efficiently.

The resulting optimization algorithm (called alternating projections) is globally convergent with a linear convergence rate to a locally optimal solution of the weighted low-rank approximation problem. Starting value for the P (or L ) parameter should be given. The iteration is stopped when a user defined convergence condition is satisfied.

Matlab implementation of the alternating projections algorithm for weighted low-rank approximation:

Variable projections algorithm

The alternating projections algorithm exploits the fact that the low rank approximation problem, parameterized in the image form, is bilinear in the variables P or L . The bilinear nature of the problem is effectively used in an alternative approach, called variable projections.

Consider again the weighted low rank approximation problem, parameterized in the image form. Minimization with respect to the L variable (a linear least squares problem) leads to the closed form expression of the approximation error as a function of P

f ( P ) = vec ⊤ ⁡ ( D ) ( W − W ( I n ⊗ P ) ( ( I n ⊗ P ) ⊤ W ( I n ⊗ P ) ) − 1 ( I n ⊗ P ) ⊤ W ) vec ⁡ ( D ) .

The original problem is therefore equivalent to the nonlinear least squares problem of minimizing f ( P ) with respect to P . For this purpose standard optimization methods, e.g. the Levenberg-Marquardt algorithm can be used.

Matlab implementation of the variable projections algorithm for weighted low-rank approximation:

The variable projections approach can be applied also to low rank approximation problems parameterized in the kernel form. The method is effective when the number of eliminated variables is much larger than the number of optimization variables left at the stage of the nonlinear least squares minimization. Such problems occur in system identification, parameterized in the kernel form, where the eliminated variables are the approximating trajectory and the remaining variables are the model parameters. In the context of linear time-invariant systems, the elimination step is equivalent to Kalman smoothing.

A Variant: convex-restricted low rank approximation

Usually, we want our new solution not only to be of low rank, but also satisfy other convex constraints due to application requirements. Our interested problem would be as follows,

minimize over p ^ ∥ p − p ^ ∥ subject to rank ⁡ ( S ( p ^ ) ) ≤ r and g ( p ^ ) ≤ 0

This problem can find tons of real applications, including to recover a good solution from a inexact (semidefinite programming) relaxation. If additional constraint g ( p ^ ) ≤ 0 is linear, like we require all elements to be nonnegative, the problem is called structured low rank approximation. And the more general form is named as convex-restricted low rank approximation.

This problem is helpful in solving many problems. However, it is challenging due to the combination of the convex and nonconvex (low-rank) constraints. Different techniques were developed based on different realizations of g ( p ^ ) ≤ 0 . However, the Alternating Direction Method of Multipliers (ADMM) can be applied to solve the nonconvex problem with convex objective function, rank constraints and other convex constraints, and is thus suitable to solve our above problem. Moreover, unlike the general nonconvex problems, ADMM will guarantee to converge a feasible solution as long as its dual variable converges in the iterations

References

Low-rank approximation Wikipedia

(Text) CC BY-SA

Contents