Given $m\geq n \geq k$ and $A \in M^{m\times n}(\mathbb{C})$, the problem asks to evaluate

$$\inf_{\textrm{rank}(B)\leq k}||A-B||$$

and gives condition on $A$ making the above minimum is taken by some unique $B$. Here $||\cdot||$ denotes standard spectral norm of a matrix, i.e. the norm of a linear functional defined by regarding matrix as linear transform between Euclidean spaces with canonical Euclidean norm.

It is quite clear if we apply Singular Value Decomposition to $A$, we will find $$\inf_{\mathrm{rank}(B)\leq k}||A-B||\leq \sigma_{k+1}$$ where $\sigma_1\geq\sigma_2\geq\cdots\geq\sigma_n\geq0$ denotes the singular value of $A$, and define $\sigma_{n+1}=0$. But I am not sure if the inequality is actually equality since I do not see an approach to discuss how spectral radius changes by perturbing with a matrix of given rank.


In what follows I assume that rank$(A)=s>k$ (otherwise, the claim follows trivially, since we can pick $B=A$ and $\sigma_{k+1}=0$).

For any $C\in M^{m\times n}(\mathbb{C})$ and $z\in\mathbb{C}^n$,

$$||C||:=\sup_{x\in\mathbb{C}^n}\frac{||Cx||}{||x||}\geq \frac{||Cz||}{||z||}.$$

Hence, it is sufficient to show that for any $B\in M^{m\times n}$ such that rank$(B)\leq k$, there exists some $z\in\mathbb{R}^n$ such that

$$||(A-B)z||\geq \sigma_{k+1}.$$

Then, by SVD, we have that

$$A=U\Sigma V^T = \sum_{i=1}^s\sigma_iu_iv_i^T,$$

where $\sigma_1\geq\sigma_2\geq\dots\geq \sigma_s$ and $\{u_1,\dots,u_s\}$ and $\{v_1,\dots,v_s\}$ are orthonormal sets of vectors.

Let $B\in M^{m\times n}$ be such that rank$(B)\leq k$. The dimension of the nullspace $B$ is greater or equal to $n-k$ while that of the span of $\{v_1,\dots,v_{k+1}\}$ is equal to $k+1$. Hence, this two subspaces intersect. Hence, there is some vector $z\in\mathbb{C}^n$ of unit length such that

$$Bz=0,\quad\quad z\in\textrm{span}\{v_1,\dots,v_{k+1}\}.$$



Since $\{u_1,\dots,u_s\}$ and $\{v_1,\dots,v_s\}$ are orthonormal sets of vectors,

$$||(A-B)z||^2=\left(\sum_{i=1}^{k+1}\sigma_i z^Tv_iu_i^T\right)\left(\sum_{i=1}^{k+1}\sigma_i u_iv_i^Tz\right)=\sum_{i=1}^{k+1}\sigma_i^2(v_i^Tz)^2\geq \sigma_{k+1}^2||z||^2.$$

  • $\begingroup$ I see in the proof you have proved: for $\forall B$ with $\textrm{rank}(B)=k$, $||A-B||\geq \sum_{i=1}^{k+1}\sigma^2_i$, taking inf we have $\inf_{B}||A-B||\geq \sum_{i=1}^{k+1}\sigma^2_i$, which, combined with my estimate deduces something wield... $\endgroup$ – Roy Han Aug 12 '13 at 14:57
  • $\begingroup$ Sorry, $1=v_i^Tv_i\neq v_iv_i^T$ (typo in my head ><), see edited answer. $\endgroup$ – jkn Aug 12 '13 at 15:17
  • 1
    $\begingroup$ Now I got your idea of choosing $\{v_1,\cdots,v_{k+1}\}$, thanks a lot! $\endgroup$ – Roy Han Aug 12 '13 at 15:34
  • $\begingroup$ And what do you think about the condition that ensures that only one $B$ exists for minimizing the norm? $\endgroup$ – Roy Han Aug 12 '13 at 15:39
  • $\begingroup$ Well, I don't think the above is enough to ensure uniqueness. Consider $$A=\begin{bmatrix}1&0\\0&1\end{bmatrix}$$ and its rank less than one approximations $$B_1=\begin{bmatrix}1&0\\0&0\end{bmatrix},\quad\quad B_2=\begin{bmatrix}0&0\\0&0\end{bmatrix}.$$ $\endgroup$ – jkn Aug 12 '13 at 16:53

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.