Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
The Eckart-Young-Mirsky theorem is sometimes stated with rank $\le k$ and sometimes with rank $= k$. Why?
More specifically, given a matrix $X \in \mathbb{R}^{n \times d}$, and a natural number $k \le \text{rank}(X)$, why are the following two optimization problems equivalent:
$$\min_{A \in \mathbb{R}^{n \times d},\;\text{rank}(A) \le k}\|X-A\|^2_F$$
$$\min_{A \in \mathbb{R}^{n \times d},\;\text{rank}(A) = k}\|X-A\|^2_F$$
I provided a proof of the Eckart-Young theorem in my answer to What norm of the reconstruction error is minimized by the low-rank approximation matrix obtained with PCA?. Let's take a look at the first steps of this proof:
We want to find matrix $A$ of rank $k$ that minimizes $\|X-A\|^2_F$. We can factorize $A=BW^\top$, where $W$ has $k$ orthonormal columns. Minimizing $\|X-BW^\top\|^2$ for fixed $W$ is a regression problem with solution $B=XW$. Plugging it in, we see that we now need to minimize $\|X-XWW^\top\|^2=\ldots$
This seems to use your formulation #2.
But what would change if we use formulation #1? Matrix $A$ of rank $\le k$ can still be factorized as $A=BW^\top$ where $W$ has $k$ orthonormal columns; if $\text{rank}(A)<k$ then some columns of $B$ will be zero. In any case, we immediately find that the optimal $B$ is given by $B=XW$.
So nothing at all changes in the proof after that. The best approximation of rank $\le k$ turns out to have rank $k$.
The purpose of this answer is to show (a) the result is far more general and (b) when you look at it the right way, it is obvious: because the matrices of rank less than $k$ occupy a negligible portion of the space of matrices of ranks less than or equal to $k$ (their complement is dense), you can never do any worse when you optimize a continuous function over the higher-rank matrices alone.
I hope that pointing this out will suffice, but for completeness the rest of this post provides some details and explanation.
It is enough to consider the set $\mathcal X$ of $n\times d$ matrices as a topological space (determined by the Frobenius norm in this case) and the set of matrices of rank $k$ or less, $\mathcal{X}^k\subset \mathcal X,$ to be a subspace. All we need to know about the function
$$f:\mathcal X\to \mathbb{R}$$
given by
$$f(X) = ||X-A||^2$$
is that it is continuous--and I hope this is obvious.
The general principle is this:
When $\mathcal{Y}\subset \mathcal{X}$ is dense and $f:\mathcal{X}\to \mathbb R$ is continuous, then $\sup f(\mathcal Y) = \sup f(\mathcal X).$
I call this a "principle" rather than a "theorem" because (a) it follows directly from the definitions, yet (b) is of widespread applicability and helpfulness, despite its obviousness. Before demonstrating this principle, let's apply it in an obvious and trivial way.
Corollary: The supremum of a continuous function on a dense subset of a topological space is never less than its supremum on the complement of that subset.
Let's deal with (a). "Dense" means that every $x\in\mathcal X$ can be approached arbitrarily closely by elements of $\mathcal Y.$ "Continuous" means values $f(x)$ can be approached arbitrarily closely by $f(z)$ where $z$ is "close" to $x$ in $\mathcal X.$ Put the two definitions together and the principle follows.
Now let's apply the corollary to $\mathcal Y^k = \mathcal X^k \setminus \mathcal X^{k-1},$ which is the set of matrices of rank $k.$
Lemma: When $k \lt \min(n,d),$ $\mathcal Y^k$ is dense in $\mathcal X^k.$
I offer two demonstrations. Algebra teaches us that $\mathcal{X}^{k}$ is the intersection of zeros of polynomial functions: namely, determinants of the $k\times k$ minors of the matrices. It is easy to see these functions are algebraically independent and are $(n-k+1)(d-k+1)$ in number. Thus locally $\mathcal{X}^k$ is a manifold of dimension $nd - (n-k+1)(d-k+1).$ Since these dimensions strictly increase as $k$ ranges from $0$ to $\min(n,d),$ the complement of each $\mathcal{X}^{k-1}$ is dense within its containing $\mathcal{X}^{k}.$
The second demonstration views $X$ as representing a linear transformation from $\mathbb{R}^d$ to $\mathbb{R}^n.$ If it is not of full rank (as assumed in the Lemma), it has nontrivial kernel and nontrivial cokernel. That is, there is a nonzero vector $x\in\mathbb{R}^d$ for which $Xx=0$ and there is a nonzero vector $y\in\mathbb{R}^n$ independent of the set of $\{Xx\mid x\in\mathbb{R}^d\}$ (this is the "column space" of $X$).
For every real number $\lambda$ define
$$X(\lambda) = X + \lambda y x^\prime.$$
Geometrically, this is altering $X$ by taking one of the directions it collapses ($x$) and instead mapping it to a new direction $y$ in the image, because
$$X(\lambda)x = (X + \lambda y x^\prime)x = Xx + \lambda y x^\prime x = 0 + \lambda(x^\prime x) y = (\lambda\, xx^\prime)y$$
is a nonzero multiple of $y.$
The dimensions of the kernel and cokernel of $X(\lambda)$ are thereby both decreased, making its rank one greater than the rank of $X.$ By choosing a sequence of nonzero values of $\lambda$ converging to $0$ we obtain a sequence $X(\lambda)$ of higher-rank matrices converging (in the Frobenius norm) to the original matrix $X,$ QED.
