Let $\bf A$ be an $n \times n$ matrix with rank $r$ where $r<n$. How can I get a full-rank approximation for $\bf A$? In other words, I want to find the rank-$n$ $\bf X$ that minimizes the Frobenius norm $\|\bf A-\bf X\|_{\text{F}}$.
$\begingroup$
$\endgroup$
7
-
4$\begingroup$ You can't minimize it (but you can make it arbitrarily small). Proof: $A + tI_N$ has full rank for infinitely many $t\in(-\epsilon,\epsilon)$ no matter how small $\epsilon\gt 0$ might be, and the norm of the difference is proportional to $\epsilon.$ This is the basis for many regularization techniques. The same result holds upon replacing the identity $I_N$ by any full-rank matrix, giving a huge variety of solutions to choose from. $\endgroup$– whuber ♦Commented May 8, 2023 at 16:30
-
$\begingroup$ So the matrix $\mathbf{A}$ is not even assumed to bei symmetric? $\endgroup$– YvesCommented May 8, 2023 at 17:53
-
$\begingroup$ @Yves Why would symmetry be interesting? $\endgroup$– Rodrigo de AzevedoCommented May 8, 2023 at 19:04
-
1$\begingroup$ @RodrigodeAzevedo Well the question relates to the singular values of the matrix $\mathbf{A}$, and if the matrix is symmetric we simply have to consider the eigenvalues. Although this makes little difference in terms of math, this may give hints on the goal. Also as suggested by comments and answers the fact that the matrix is square may quite confusely see it as a covariance matrix. $\endgroup$– YvesCommented May 8, 2023 at 19:18
-
2$\begingroup$ @RodrigodeAzevedo - not going to disagree... sometimes people post in their SE area of end use application rather than in the SE area where the problem really lies. $\endgroup$– jbowmanCommented May 8, 2023 at 19:19
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
3
As the simplest example, if we choose $B = t I_n$, then $X = A + B$ and we can make $\| A - (A + B) \|_F = \| B \|_F$ arbitrarily small according to the choice of $t$ such that $|t| > 0$. (But we can't minimize $t$ because the minimum value of $\| B \|_F$ occurs at $t=0$, for which $B$ is not full-rank.)
A wealth of interesting solutions exist for $B$ that are not scalar multiples of the identity matrix.
-
3$\begingroup$ +1 For the record, there's an elementary proof of this assertion when $B$ is the identity $I$ (and the generalization to all full-rank $B$ follows from standard linear algebra techniques): $A+tI$ is of full rank iff $\det(A+tI)\ne 0$ and that determinant is a polynomial of degree $n$ (with leading coefficient $1$), whence there are at most $n$ distinct values of $t$ where this construction fails, qed. Geometrically, the set of rank-deficient matrices is a submersed hypersurface in $\mathbb R^n,$ whence its complement contains points arbitrarily close to it. $\endgroup$– whuber ♦Commented May 8, 2023 at 16:51
-
$\begingroup$ Thanks both for the answer. As a follow-up, will this change if we add constraints on the full-rank matrix, e.g, enforcing Frobenius norm of X to be 1. $\endgroup$– MMMCommented May 8, 2023 at 16:58
-
$\begingroup$ Here, the geometric perspective is invaluable: you are asking to approximate a point in one local manifold by another in another local manifold (of codimension 1 also). Because both sets are closed, there will exist a global minimum distance and it won't generally be zero. Finding it can be numerically challenging, but generically the solution where $B$ ranges over all $n\times n$ matrices of norm $1$ will be of full rank and if it's not, you can just perturb it a tiny bit. Thus, you're minimizing a function of $n^2$ variables subject to a single simple constraint. $\endgroup$– whuber ♦Commented May 8, 2023 at 17:23