Minimisation of ||Ax|| with sparse x, ||x||=1 I need a bit of help finding search terms, keywords, or ideally even code that can be used to help me find a viable solution to the following minimisation problem.
$$^{min}_{\:\:x}\: |Ax|_2 \:\:s.t.\: |x|_2 = 1, $$
$$\:density(x)<<length(x)$$
My problem involves a large number (~100) of data types, with an even larger number of data points (~ between 500 - 2,000), that create a real matrix $A$ that is $m \mathbb{x} n$ with $m>n$. In order to avoid over-fitting, I'm looking for a vector $x$ of size $n$ that has only a few non-zero terms.
I've noted that Total Least Squares methods might be viable, but all the papers I've found on Sparse TLS solving use an equation of the form $Ax=b$, and I worry that as my $b$ term is zero, this may prove to cause issues in any implementation I attempt.
notes on A: A is not sparse. A does not have a kernel. A is an Alternant matrix of lipschitz continuous functions on a fairly fine grid. Each column of A has magnitude equal to the length of that column.
 A: You could try solving the regularized problem:
\begin{align}
\min~~&\|Ax\|_2 + \lambda\|x\|_1\\[1mm]
\text{s.t.}~~& \|x\|_2 = 1
\end{align}
where $\lambda$ is some nonzero scalar. The addition of the $1$-norm term $\|x\|_1$ tends to induce sparsity in the solution. The scalar $\lambda$ controls the importance of the regularization term. You can read more about this here - look under the section Regularizers for sparsity. If $A$ is not too large then you can check how close you are to the optimal non-sparse solution $(\lambda = 0)$ by computing the singular values of $A$ and comparing with $\sigma_n$.
A: I think you can't dictate sparseness of a solution of a minimization problem?! 
E.g. if the minimization problem would be the maximum absolute value of $x_i$, the solution would be something with all $x_i$ equal to $\frac{1}{\sqrt{N}}$
Unless you are willing to sacrifice optimality for sparseness, then you could fiddle with your optimization algorithm, e.g. add a cost function for non-zero elements in $x$. I'm not sure how to do that in your case.
