Given The unstructured problem with fit measured by the Frobenius norm, i.e., has an 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.
This problem was originally solved by Erhard Schmidt[1] in the infinite dimensional context of integral operators (although his methods easily generalize to arbitrary compact operators on Hilbert spaces) and later rediscovered by C. Eckart and G.
[2] L. Mirsky generalized the result to arbitrary unitarily invariant norms.
matrix, obtained from the truncated singular value decomposition is such that The minimizer
Therefore, The result follows by taking the square root of both sides of the above inequality.
The Frobenius norm weights uniformly all elements of the approximation error
Prior knowledge about distribution of the errors can be taken into account by considering the weighted low-rank approximation problem where
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.
[6][7] One of the important ideas been used is called Oblivious Subspace Embedding (OSE), it is first proposed by Sarlos.
Such distances matrices are commonly computed in software packages and have applications to learning image manifolds, handwriting recognition, and multi-dimensional unfolding.
In an attempt to reduce their description size,[12][13] one can study low rank approximation of such matrices.
The low-rank approximation problems in the distributed and streaming setting has been considered in.
The image representation of the rank constraint suggests a parameter optimization method in which the cost function is minimized alternatively over one of the variables (
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.
The iteration is stopped when a user defined convergence condition is satisfied.
Matlab implementation of the alternating projections algorithm for weighted low-rank approximation: The alternating projections algorithm exploits the fact that the low rank approximation problem, parameterized in the image form, is bilinear in the variables
The bilinear nature of the problem is effectively used in an alternative approach, called variable projections.
[15] Consider again the weighted low rank approximation problem, parameterized in the image form.
variable (a linear least squares problem) leads to the closed form expression of the approximation error as a function of
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.
Usually, we want our new solution not only to be of low rank, but also satisfy other convex constraints due to application requirements.
is linear, like we require all elements to be nonnegative, the problem is called structured low rank approximation.
[16] The more general form is named convex-restricted low rank approximation.
However, it is challenging due to the combination of the convex and nonconvex (low-rank) constraints.
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,[17] and is thus suitable to solve our above problem.