For any matrix $M$, denote by $\sigma_{\min}(M)$ the smallest non-zero singular value of $M$. Now given a matrix $A=[A1,A2]$ and assume that $A$ has full column rank. Is it always true that $\sigma_{\min}(A)\leq\sigma_{\min}(A_1)$? I tried several examples on Matlab and all turned to be true. But I cannot prove it yet. Thanks in advance!


Adding a column $z$ to a matrix $A\in \mathbb{R}^{m \times n}$, $m>n$, will cause the min singular value ($\sigma_{min})$ to decrease or stay the same i.e., $$\sigma_{min}([A | z]) \leq \sigma_{min}(A)$$


Taking $A = U\Sigma V^T$ (the SVD) and $x$ as the last column of $V$, which corresponds to the singular vector for $\sigma_{min}$, and $\hat{A} = [A|z]$, we have

\begin{align} \sigma_{min}(A)& = \|Ax\|_2 && \text{b/c $x:=$ last column of $V$}\\ &= \|\hat{A}\begin{bmatrix}x\\0\end{bmatrix}\|_2 \ \geq \ \sigma_{min}(\hat{A})\cdot\|\begin{bmatrix}x\\0\end{bmatrix}\|_2 && \text{b/c $\|Ax\|_2 \geq \sigma_{min} \|x\|_2 $ and $ \|x\|_2=1$} \\ &= \sigma_{min}(\hat{A}) \cdot 1 && \text{} \end{align} Thus, $$\sigma_{min}(\hat{A}) \leq \sigma_{min}(A)$$

This is for the case of adding a column; I am not sure if your A2 is a matrix or vector, but the derivation should be similar. For reference, I took a similar approach from Golub's Matrix Computations 4th edition section 2.4.2


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.