5
$\begingroup$

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$$

$\endgroup$
1
  • $\begingroup$ In fact, I was trying to understand a proof of the first formulation, but in the proof they switched somehow (not directly) to the second formulation. Here is the proof (and the part that I do not understand is highlighted): ibb.co/cwKeVU . I took a look at your link, but I think that they proved the second formulation instead of the first one: "... matrix A of rank k that minimizes...", "... where W has k orthonormal columns..." . $\endgroup$
    – user_anon
    Sep 13, 2018 at 7:11

2 Answers 2

4
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ +1 Nice. Matrices of rank $<k$ form a lower-dimensional manifold in the space of matrices of rank $\le k$, so for any continuous $f(X)$ the suprema over $\{X|\text{rank}(X)\le k\}$ and over $\{X|\text{rank}(X)= k\}$ are the same. But it still might be true the maximum of $f(X)$ lies exactly on this lower-dimensional manifold. Your argument does not show it can't. $\endgroup$
    – amoeba
    Sep 20, 2018 at 15:26
  • $\begingroup$ @Amoeba That is correct--but there's no problem with that, because the supremum over the larger space will still coincide with the maximum found on the lower-dimensional space in that case. That's the point of the somewhat elliptical phrase "cannot do any worse." $\endgroup$
    – whuber
    Sep 20, 2018 at 15:30
  • $\begingroup$ Sure, but in what sense is it "no problem"? One might still want to know whether the maximum lies on a submanifold or not. Are you saying that there is no difference from the numerical point of view, because a numerical optimizer constrained to search over the dense set will get within the machine error to the maximum? (I double-checked for typos, but please do fix them if you see any, not to confuse further readers.) $\endgroup$
    – amoeba
    Sep 20, 2018 at 15:35
  • $\begingroup$ @Amoeba You seem to be pursuing questions that haven't been asked. The only issue here is why it makes no difference to find the supremum of a continuous function over the set of rank $k$ matrices or over the set of matrices of rank up to $k$: "why are the two optimization problems equivalent?" I am only trying to show that they owe their equivalence to some elementary topological properties of the domains and objective function rather than to any deep or specialized algebraic decompositions of matrices. $\endgroup$
    – whuber
    Sep 20, 2018 at 19:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.