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