Given a vector $x \in \mathbb{R}^{m}$, let $\theta(x)$ be the number of sign changes in the sequence: $$x_{1},x_{2}...x_{m}$$ For example, vector $x = \left [1,3,-1,2,4 \right ]^{T}$ has $\theta(x)=2$.
Given a full column rank matrix $A \in \mathbb{R}^{m\times n}$ and a vector $b \in \mathbb{R}^{n}$, I seek for the least squares solution $x_{N}$ of the linear system $Ax=b$ on the set defined by $\theta(x)=N$.
Equivalently, for a given number $N$ of sign changes in $x$, which is the element $x_{N}$ that minimizes $\left \| Ax-b \right \|$ ?
If $m$ and $n$ are small, a brute-force solution is feasible, by solving all combinations of the QP optimization $\min \left \| Ax-b \right \|^{2}$ on $x_{1}\lessgtr0,x_{2}\lessgtr0,etc$ for a given $N$. However, when the system gets bigger (in my situation I have $m,n>100$) the number of cases grows with a binomial coefficient and the brute-force solution becomes computationally unfeasible.
Is there a more efficient way to solve this problem?
Thank you!