Minimize sum of absolute value with linear constraint Consider a minimization problem:
$$
\begin{aligned}
& \min \sum_{i=1}^n |x_i|,\\
& A x = b,
\end{aligned}
$$
where $A$ is an $m\times n$ matrix of rank $m$.
I know that the minimum points contains one where at least $n-m$ components of $x$ is zero and I have proved this conclusion. My problem is that, I think this should be a developed proposition but I am not familiar with optimization theory, so I don't know where to find a reference. Could anybody help me find a reference like a book or article? Thanks!
 A: One standard linearization of absolute value is to introduce a new variable $y_i$ to represent $|x_i|$, and the resulting linear programming (LP) problem is to minimize $\sum_{i=1}^n y_i$ subject to
\begin{align}
Ax &= b \\
y_i &\ge  x_i &&\text{for all $i$}\\
y_i &\ge -x_i &&\text{for all $i$}
\end{align}
This LP has $2n$ variables and $m+2n$ constraints.  A standard result from LP theory is that there exists an optimal solution with at most $m+2n$ nonzero values.
A different standard linearization of absolute value is to introduce two new nonnegative variables $x_i^+$ and $x_i^-$ to represent $|x_i|$, and the resulting LP is to minimize $\sum_{i=1}^n (x_i^+ + x_i^-)$ subject to
$A(x^+ - x^-) = b$.
This LP has $2n$ variables and $m$ constraints.  A standard result from LP theory is that there exists an optimal solution with at most $m$ nonzero values, hence at least $2n-m$ zero values, hence at least $(2n-m)-n=n-m$ zero values among the original $x_i$ variables.  (Note that $x_i^+ x_i^- = 0$ at optimality because otherwise we can improve the objective value and preserve feasibility by decreasing both $x_i^+$ and $x_i^-$ by the same amount, but this observation is not required to obtain the desired result.)
A: Here is an relevant result. I have seen similar constructions in many LP related proofs (mostly showing equivalence of basic feasible solutions and extreme points), but never as an explicit result.
Suppose $S$ is a linear subspace of dimension $l$ and $x^* \in \mathbb{R}^n$ has $p<l$ zeros. Then there is some $h^* \in S$ such that $\|x^*+h^*\|_1 \le \|x^*\|_1$ and $x^*+h^*$ has at least $p+1$ zeros.
Let $T= \operatorname{sp} \{ e_k \}_{x^*_k \neq 0}$, that is the subspace spanned by the unit vectors corresponding to the non zero elements of $x^*$.
Note that $\dim T = n-p > n-l$. Note that $x^* \in T$ and that
$\dim S \cap T \ge 1$.
For any non zero $h \in T$, let $T = \inf \{ -{x_k \over h_k} | h_k \neq 0, {x_k \over h_k} = {|x_k| \over (\operatorname{sgn} x^*_K)h_k} <0 \}$. $T$ may be infinite, but $0 < T$.
If  $0 \le t \le T$, then $\|x^*+th\|_1 = \sum_k (\operatorname{sgn} x^*_k)(x^*_k+th_k) = \|x\|_1+t \sum_k (\operatorname{sgn} x^*_k) h_k$.
Let $d=(\operatorname{sgn} x^*_1, \cdots, \operatorname{sgn} x^*_n)$ and note that as long as $h \in T$, $h \neq 0$, $d^T h \le 0$ and $t \in [0,T]$ then
$\|x^*+th\|_1 \le \|x^*\|_1$. Furthermore, in this case we must have $T<\infty$ and at least one component of $x^*+Th$ is zero.
Finally, since $S \cap T$ must have a non trivial intersection with the closed halfspace $H=\{ h | d^T h \le 0 \}$, we can find some non zero $h \in S \cap T \cap H$, and letting $h^* = Th$ as above, we see that
$\|x^*+h^*\|_1 \le \|x^*\|_1$ and $x^*+h^*$ has at least $p+1$ zeros.
In particular, if $S$ is a linear subspace of dimension $l$ and $x^* \in \mathbb{R}^n$ then there is some $h^* \in S$ such that $\|x^*+h^*\|_1 \le \|x^*\|_1$ and $x^*+h^*$ has at least $l$ zeros.
Finally, suppose $x^*$ is a solution to the problem in the question. Note that with $S= \ker A$, we have $l = \dim S = n-m$. Hence there is some $h^* \in S$ such that $x^*+h^*$ has at least $l=n-m$ zeros and $\|x^*+h^*\|_1 \le \|x^*\|_1$. Since $x^*+h^*$ is feasible and $x^*$ is a solution, we must have
$\|x^*+h^*\|_1 = \|x^*\|_1$.
