Low-rank matrix approximation in terms of entry-wise $L_1$ norm According to the Eckart–Young theorem, the low-rank matrix approximation problem $$\min_{\tilde{A}} \quad \| A - \tilde{A} \|_F \quad \text{s.t.} \quad \text{rank}(\tilde{A}) \le r$$ is given by the SVD of $A$, where $\| \cdot \|_F$ denotes the Frobenius norm.
I think if the the Frobenius norm is replaced by the nuclear norm, the solution will not change, but I wonder whether there is an analytic solution when the Frobenius norm (entry-wise $L_2$ norm) is replaced by the entry-wise $L_1$ norm. Note that the entry-wise $L_1$ norm is NOT the nuclear norm.
 A: The solution to the problem $$\min_{\tilde{A}} \quad \| A - \tilde{A} \| \quad \text{s.t.} \quad \text{rank}(\tilde{A}) \le r$$ is given by SVD as you say for any norm $\|\cdot\|$ that is unitarily invariant, i.e. invariant under unitary transformations. This is true of any norm that's a vector norm in the eigenvalues/singular values since unitary transformations do not affect the spectrum, e.g. Frobenius norm (2-norm in spectrum) or nuclear norm (1-norm in spectrum) or operator norm (infinity-norm in spectrum).
To my knowledge, there is no closed form for the entry-wise 1-norm. What is often done for these harder norms (most common case is the Frobenius norm on a limited support, i.e. minimize entry-wise squared distance from a partially observed matrix where the distance is only taken on the entries observed; this is the noisy low-rank matrix completion problem) is to optimize $$\min_{\tilde{A}} \quad \| A - \tilde{A} \|+\lambda\|\tilde A\|_*$$ where * is the nuclear norm. This is because the nuclear norm is convex envelope of rank on the operator norm ball. For the noisy matrix completion problem there are a bunch of guarantees on recovery of the minimal rank matrix in terms of restricted isometry conditions (google restricted isometry and matrix rank). This problem can be solved by a SDP and it is also exactly in the formulation appropriate for accelerated first order methods.
For an exact solution, you'd have to do some sort of SDP branch and bound or write the problem in terms of the low-rank factorization of $\tilde A$ and solve a potentially non-convex quadratic program perhaps by using iterative linearizations (fix the left factor then it's linear so easily solve, fix right factor, solve, repeat).
A: The answer is yes, and egosphere is right. This paper is what you were looking for: Mirsky-1960
A: This question has been partially answered from several different perspectives(approximation algorithm, hardness) in a recent work 
https://arxiv.org/abs/1611.00898
Low Rank Approximation with Entrywise $\ell_1$-Norm Error. (To appear in STOC 2017)
