Is there a tractable solution to the optimization problem
$$\min \|Ax\|_1 \mbox{ such that } \|x\|_2^2 = 1?$$
Because of the non-convexity of the equality constraint, it seems like this is hard. (In my specific application, $x$ is just $3$-dimensional, but the number of rows of $A$ can be large.)
Edit: The reason I introduced the $\|x\|_2^2 = 1$ constraint is to avoid the trivial solution $x = 0$. There might be other ways to avoid it, potentially leading to a different but equally practically useful solution. Any ideas?
Edit 2: Geometrically, the rows of $A$ are points, and we are looking for a plane that fits them. The points fall roughly into two groups: ones that fit a plane very well, and others that do not fit at all. The 1-norm seems better suited to such a fit than simple least squares.