# Minimizing maximum absolute column sum norm of the residual between a matrix and its $k$-rank approximation

Let $X \in \mathbb{R}^{m\times n}$ be a matrix with rank $r$.

How can we find the optimal $\tilde{X} \in \mathbb{R}^{m\times n}$ whose rank is $k$ where $k\leq r$ and the reconstruction error in terms of maximum absolute column sum norm is minimized? That is

$$e=\|X-\tilde{X}\|_1 = \max_j \sum_i|X_{ij}-\tilde{X}_{ij}|$$

is minimized.

I know that the optimal solution is the $k$-reduced SVD when Frobenius-norm or spectral norm is minimized. But I'm not familiar with optimization related to $l_1$-norm and I want to use it to find sparse bases to use in an audio processing project.

Is there an analytic closed form solution for this problem? Or can I find the $k$-rank approximation in an iterative numerical method?

-
The constraint $\textbf{rank}(\tilde{X}) \leq k$ seems difficult, because the rank function is not convex. Could you modify the problem to avoid this? For example, would you be happy to obtain a low-rank approximation to $X$? Penalizing the "nuclear norm" of $\tilde{X}$ in your objective function will encourage the optimal value to be low-rank. – littleO Nov 6 '12 at 10:40
Thank you very much for the comment. Actually, this was the problem we were discussing in our reading group. That's why I wanted to learn if there's an already known way to solve it. – petrichor Nov 6 '12 at 13:25