How to find a matrix perturbation which lowers the rank of a matrix

Question

I have a matrix $A \in \mathbb{R}^{m x n}$ which has independent columns.
I want to find the smallest perturbation which will make it have a kernel and a vector in that kernel.
Something like

$$ \min_{x, E} \| E \|_F \quad \text{s.t.} \quad ( A + E ) x = 0 $$

How can I find $x$?

My gut tells me it will be given by the SVD, I am just not sure how to formulate this.

Answer 1

Sketching a solution:

1. Minimizng the Frobenius norm of $\boldsymbol{E}$ is equivalent to finding $\hat{\boldsymbol{A}}$ such that $\arg \min_{ \hat{\boldsymbol{A}}, \operatorname{rank} \left( \hat{\boldsymbol{A}} \right) = n - 1 } \frac{1}{2} {\left\| \hat{\boldsymbol{A}} - \boldsymbol{A} \right\|}_{F}^{2} $.
2. By Eckart Young Mirsky theorem it is given by the partial reconstruction of $\boldsymbol{A}$ using SVD (Zeroing the last singular vector).
3. The singluar vector of (2) is the vector which spans the kernel of $\hat{\boldsymbol{A}}$ which is the $\boldsymbol{x}$ you're after (Assuming it is asked in a normalized form).