Why does compressed sensing work? Because the $\ell_1$ ball in high dimensions is extremely "pointy" -- the extreme values of a linear function on this ball are very likely to be attained on the faces of low dimensions, those that consist of sparse vectors. When applied to matrices, the sparseness of the set of eigenvalues means low rank, as @mrig wrote before me.
In general the Frobenius and nuclear norm are not a good proxy for rank. The norms depend on the singular values $||X||_* = \sum_i \sigma_i(X)$ and $||X||_F^2 = \sum_i \sigma_i^2(X)$... so if the singular values of your matrix are all too small or too large, then you have a bad approximation to the rank.
However, you are right that when the singular values are clustered somewhere near one both norms can give a good approximation of the rank. Lets look at a bound...
If the $r$ nonzero singular values $\sigma_1,...,\sigma_r$ of a rank $r$ matrix $X$ are bounded by $|1-\sigma_i| \leq \epsilon/r$ for a error tolerance $0\leq\epsilon<r$, then $|r - ||X||_*| \leq \epsilon$. This bound tells us that as the your error in the approximation of the rank grows, the singular values can correspondingly grow linearly.
For the Frobenius norm: If the $r$ nonzero singular values $\sigma_1,...,\sigma_r$ of a rank $r$ matrix $X$ are bounded by $\sqrt{1-\epsilon/r}\leq\sigma_i\leq\sqrt{1+\epsilon/r}$, then $|r - ||X||_*| \leq \epsilon$. In this case if we increase our approximation error tolerance, our singular values can only grow according to this square root function.
In other words, these bounds show that regardless of norm choice you don't have a lot of wiggle room in your singular values if you want your norm to well approximate rank. However, for the nuclear norm you have more wiggle room than Frobenius.
A good rule of thumb is that the nuclear norm can achieve the same approximation to rank as the Frobenius rule with about twice as much freedom in singular values(interval twice as large), and that the singular values should always be near one.
In your minimization problem, it is hard to know how to constrain $X$ to ensure well approximation of the rank. Perhaps normalizing the spectral radius of $A$ and $B$ could help, or constraining $X$ with the spectral norm $||Ax||/||x||$.
Best Answer
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).