= Low-rank approximation
{title2=$\min_{\operatorname{rank}B\leq r}\|A-B\|$}
{wiki}
A low-rank approximation replaces an $m\times n$ <matrix> $A$ by a <matrix> $B$ of <matrix rank> at most a chosen integer $r$, with $0\leq r\leq\min(m,n)$, while making an explicitly chosen error <norm> small. The point is to describe many entries using a few shared patterns: an <image compression> may retain broad brightness patterns while discarding finer ones. The approximation is useful when the saved storage or computation justifies the lost detail. A small <matrix rank> alone says nothing about the error.
The compact representation is a sum of <outer products>, equivalently a product of two thin <matrices>:
$$
B=XY^*=\sum_{j=1}^r x_jy_j^*,\qquad
X\in\mathbb C^{m\times r},\quad Y\in\mathbb C^{n\times r}.
$$
Here $x_j,y_j$ are the columns of $X,Y$, and the star denotes the <conjugate transpose>; over the <real numbers> use the <transpose>. The <rank bound for a matrix product> gives $\operatorname{rank}B\leq r$. Conversely, choose a <basis> of the <column space> of $B$ as the columns of $X$, and put the coordinates of each column of $B$ into $Y^*$; pad with zero columns if the <matrix rank> is smaller than $r$. Each nonzero <outer product> is a <rank-one matrix>: it repeats a single column pattern at different strengths across the columns.
Keeping the two factors stores $r(m+n)$ <scalars> instead of $mn$. This saves space only when $r(m+n)<mn$. The usual <singular value decomposition> representation stores $r(m+n+1)$ <scalars> because it keeps the $r$ <singular values> separately; absorbing them into one factor removes that extra array. These are representation sizes at equal <scalar> precision, before file overhead. See https://link.springer.com/chapter/10.1007/978-3-030-31351-7_9[Uschmajew and Vandereycken, §9.2: thin factors and their storage], and https://cs357.cs.illinois.edu/notes/ref-16-svd.html[Illinois CS 357, Low-rank approximation: storing singular vectors and values].
The factors also give $Bz=X(Y^*z)$ without forming the full <matrix> $B$. Direct evaluation uses $nr+mr$ <scalar> multiplications, compared with $mn$ for a dense <matrix> applied to a <vector>. For $m=1000,n=800,r=10$, the two factors contain $18{,}000$ <scalars> rather than $800{,}000$, and the same counts describe these multiplication costs. Constructing the factors is a separate cost. Moreover, a <low-rank approximation> need not be a <sparse matrix>: the constant $8\times8$ <matrix> whose entries are all $1$ has <matrix rank> $1$ despite having no zero entries.
For the standard unweighted problem, write a <singular value decomposition> with $p=\min(m,n)$ and <singular values> $\sigma_1\geq\cdots\geq\sigma_p\geq0$. Retain the first $r$ paired <left singular vectors> and <right singular vectors>:
$$
A_r=\sum_{j=1}^r\sigma_j u_jv_j^*,\qquad A_0=0.
$$
The <Eckart-Young-Mirsky theorem> says that this same $A_r$ minimizes both of the following error <norms> over all <matrices> with <matrix rank> at most $r$:
$$
\min_{\operatorname{rank}B\leq r}\|A-B\|_F
=\|A-A_r\|_F=\left(\sum_{j=r+1}^p\sigma_j^2\right)^{1/2},
\qquad
\min_{\operatorname{rank}B\leq r}\|A-B\|_2
=\|A-A_r\|_2=\sigma_{r+1},
$$
where $\sigma_{p+1}=0$ and an empty sum is zero. Here the <Frobenius norm> is $\|E\|_F=(\sum_{i,j}|E_{ij}|^2)^{1/2}$, whereas the <operator norm> is specifically induced by the <Euclidean norm>, $\|E\|_2=\max_{\|z\|_2=1}\|Ez\|_2$. The first aggregates errors in all entries; the second bounds the worst output error for a <unit vector> input. These formulas apply to real and complex <matrices>. https://math.uchicago.edu/~may/REU2016/REUPapers/Mazeika.pdf[Mazeika, §§4.1 and 4.3: norms and optimal singular-value truncation]{ref}
For $A\ne0$, a relative <Frobenius norm> tolerance $\varepsilon$ is met precisely when the discarded squared <singular values> sum to at most $\varepsilon^2\sum_j\sigma_j^2$. Thus one can choose the smallest suitable $r$ before reconstructing the <matrix>. Many individually small discarded <singular values> can still have a large combined error. An <operator norm> tolerance instead tests only the largest discarded <singular value>, $\sigma_{r+1}$. The two questions can therefore select different ranks.
The following stipulated $8\times8$ <matrix> makes the tradeoff visible. Define four real <vectors> of length $8$:
$$
h_0=(1,1,1,1,1,1,1,1)^T,\quad
h_1=(1,1,1,1,-1,-1,-1,-1)^T,
$$
$$
h_2=(1,1,-1,-1,1,1,-1,-1)^T,\quad
h_3=(1,-1,1,-1,1,-1,1,-1)^T,
\qquad
A=h_0h_0^T+\frac38h_1h_1^T+\frac18h_2h_2^T+\frac1{16}h_3h_3^T.
$$
The <vectors> $h_j/\sqrt8$ are <orthonormal>, so this is already a <singular value decomposition> written as <outer products>, with positive <singular values> $8,3,1,1/2$. All entries lie between $7/16$ and $25/16$ and can be displayed as brightnesses. The first component is uniform brightness, the second distinguishes broad blocks, and the last two supply finer alternating patterns. This is a designed arithmetic example, not measured image data.
\Image[/low-rank-pattern-reconstruction.png]
{title=Shared patterns in a stipulated $8\times8$ <matrix>}
{description=The first three panels use the same brightness scale. Rank one retains uniform brightness; rank two adds the broad blocks. The signed residual $A-A_2$ has its own color scale to expose the discarded patterns. The factors apply a <linear map> through just $r$ intermediate coordinates.}
Here $A_1=h_0h_0^T$ has every entry equal to $1$, while $A_2=h_0h_0^T+3h_1h_1^T/8$ has entries $11/8$ within the two diagonal blocks and $5/8$ in the other two blocks. For instance, $A_{11}=25/16$ becomes $(A_2)_{11}=11/8$: its error is $3/16$. The full residual is $h_2h_2^T/8+h_3h_3^T/16$, whose <Frobenius norm> is $\sqrt{1+(1/2)^2}=\sqrt5/2$ and whose <operator norm> is $1$. Since $\|A\|_F=\sqrt{297}/2$, the relative <Frobenius norm> error is $\sqrt{5/297}\approx12.97\%$. Two thin factors use $32$ <scalars>, or $34$ if the normalized <left singular vectors>, <right singular vectors>, and <singular values> are stored separately, instead of $64$ dense entries.
\Image[/low-rank-error-storage-tradeoff.png]
{title=Error falls as storage rises for the stipulated <matrix>}
{description=The exact <Frobenius norm> and <operator norm> errors are plotted for $r=0,1,2,3,4$. The storage panel counts the two thin factors, or the normalized <left singular vectors> and <right singular vectors> plus separate <singular values>, at equal <scalar> precision. Lines join discrete rank choices; they do not represent intermediate ranks or measured data.}
Retaining three components reduces the <Frobenius norm> error to $1/2$ while using $48$ <scalars> in two factors. Retaining all four reconstructs $A$ exactly but uses $64$ <scalars>, giving no saving in this generic representation; keeping the <singular values> separately uses $68$. Our particular sign patterns could be encoded more economically, but that would exploit an additional structure beyond the general <low-rank approximation>. The striking feature is that numerical error and storage can both be read from the decomposition, rather than judged only by how smooth the picture looks.
The constraint is deliberately <matrix rank> \i[at most] $r$. The truncation has $\operatorname{rank}A_r=\min(r,\operatorname{rank}A)$. If $\operatorname{rank}A<r$, the best approximation is $A$ itself, with zero error. Requiring <matrix rank> exactly $r$ can destroy attainment: for $A=\operatorname{diag}(1,0)$ and $r=2$, the <matrices> $B_\delta=\operatorname{diag}(1,\delta)$ have <matrix rank> $2$ for $\delta>0$, and both error <norms> equal $\delta$. Their error has <infimum> zero, but no rank-two <matrix> attains it. If $r\leq\operatorname{rank}A$, the displayed $A_r$ does have <matrix rank> exactly $r$ and attains the same minimum under either constraint.
Optimality also does not always mean uniqueness. For $0<r<\operatorname{rank}A$, the best <Frobenius norm> approximation is unique when $\sigma_r>\sigma_{r+1}$. https://link.springer.com/chapter/10.1007/978-3-030-31351-7_9[Uschmajew and Vandereycken, Theorem 9.1: uniqueness across a singular-value gap]{ref} A positive tie across the cutoff permits different choices: for $A=\operatorname{diag}(3,3,1)$ and $r=1$, both $\operatorname{diag}(3,0,0)$ and $\operatorname{diag}(0,3,0)$ have <Frobenius norm> error $\sqrt{10}$ and <operator norm> error $3$. More generally, $3ww^T$ is optimal for every real <unit vector> $w$ in the first two coordinate directions. Rotating which tied direction is kept changes the approximation. Repeated <singular values> entirely inside the retained group do not change its sum of <outer products>. At $r=0$ the only feasible <matrix> is zero; at $r\geq\operatorname{rank}A$ the unique zero-error approximation is $A$, even if some <singular values> are tied at zero.
A strict gap does not guarantee uniqueness for the <operator norm>. For $A=\operatorname{diag}(3,1)$ and $r=1$, every $B_t=\operatorname{diag}(t,0)$ with $2\leq t\leq4$ has <matrix rank> $1$ and error $\|A-B_t\|_2=\max(|3-t|,1)=1$, which is optimal. Only $t=3$ minimizes the <Frobenius norm>, since $\|A-B_t\|_F=\sqrt{(3-t)^2+1}$. An unchanged worst direction can hide extra error in another direction under the <operator norm>.
Finally, these guarantees concern the stated <norms> and the sole <matrix rank> constraint. They do not establish that a discarded pattern is noise or irrelevant to a particular task: the finer patterns in our constructed example were put there intentionally. Adding entrywise weights or restrictions on the factors changes the problem, so the <Eckart-Young-Mirsky theorem> above does not automatically solve it. For historical context, the original 1936 matrix problem is documented in the existing <Eckart-Young-Mirsky theorem> section.
Back to article page
