# On minimizing matrix norm

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

So,

$$(A-B)z=Az=\sum_{i=1}^s\sigma_iu_iv_i^Tz=\sum_{i=1}^{k+1}\sigma_iu_iv_i^Tz.$$

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

• 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... – Roy Han Aug 12 '13 at 14:57
• Sorry, $1=v_i^Tv_i\neq v_iv_i^T$ (typo in my head ><), see edited answer. – jkn Aug 12 '13 at 15:17
• Now I got your idea of choosing $\{v_1,\cdots,v_{k+1}\}$, thanks a lot! – Roy Han Aug 12 '13 at 15:34
• And what do you think about the condition that ensures that only one $B$ exists for minimizing the norm? – Roy Han Aug 12 '13 at 15:39
• 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}.$$ – jkn Aug 12 '13 at 16:53