# Transform $a\mathbf x+\mathbf b$, then make it $k$-sparse, resulting least modification?

Consider vector $\mathbf x = (x_1,x_2,\cdots,x_n)$, $a$ a scalar, $\mathbf b = (b_0,\cdots,b_0)$ and $k < n$.

I want to transform $\mathbf x$ ($\mathbf y = a\mathbf x+\mathbf b$) such that if I set $k$ elements of the resulting vector ($\mathbf y$) to zero, it is modified as less as possible.

Or equivalently, what is the best transformation of type $\mathbf y=a\mathbf x+\mathbf b$ such that, projecting $\mathbf y$ into $k$-sparse vectors, leads to minimum change (in $\ell$-2 norm sense)? (Also what values of $\mathbf y$ are set to zero?)

Edit: Actually, this problem arouse from this original problem: Find $k$-sparse vector $\mathbf x \in \mathbb R_+^n$ which its periodic auto-correlation function (PACF) has constant sidelobes i.e. $c_1=c_2=\cdots=c_n$, where $c_n = \sum_m \tilde x_{n+m}\tilde x_m$.

One way to numerically do this is minimizing $\sum_{l=1}^{n-1}(c_l-c_{l+1})^2$ (without considering sparsity constraint) and finding a non-sparse $\mathbf x$ , then making it $k$-sparse using the transform stated in the question (since the property of constant sidelobes is preserved under this transform). So I'm looking for the best transform of this kind.

-
"modified as little as possible" in what norm? in the absolute or in the relative sense? Can you be more precise about this? – fedja Aug 21 '13 at 14:00
@fedja in $\ell$-2 norm or euclidean distance, thanks – Mahdi Khosravi Aug 21 '13 at 14:09
I believe this is NP-hard. – Igor Rivin Aug 21 '13 at 23:52
@Igor Rivin Anything wrong with my solution, then? – fedja Aug 27 '13 at 13:19
@fedja either with your solution or with my belief system :) I will ponder. – Igor Rivin Aug 27 '13 at 13:38

I'll use $a$ instead of $\mathbf x$ and $t$ instead of $a$. Formally, the problem asks to find $t$ and a subset $S$ of cardinality $k$ such that $\sum_{j\in S}(a_jt+b_j)^2$ is as small as possible. Of course, once you know the set, finding $t$ is not a problem. Also, if you know the ordering of $2n$ numbers $\pm(a_jt+b_j)$, finding $S$ is not a problem either. Now the point is that when $t$ moves from $-\infty$ to $\infty$, there are at most $2n^2$ changes of order (some 2 lines have to intersect for that), so you can list all these orders, choose the set corresponding to each order, do the trivial minimization of the quadratics for each set, and, finally, choose the least of $2n^2$ values.
If you do it intelligently, the running time is $Cn^2\log n$ because each crossing takes just constant time to update all relevant values if you sort the crossing points before starting (that's where $\log$ comes from).
Thank you for your great contribution. You know, $\mathbf b = (b_0,\cdots,b_0)$ is a part of transformation to be found, and it is not a constant. I edited the question to make it clearer. – Mahdi Khosravi Aug 29 '13 at 11:23
It makes no sense now: $a=b_0=0$ is an obvious answer. – fedja Aug 29 '13 at 11:27
Look, then I will say $a=b_0=\epsilon$ where $\epsilon$ is the machine precision. Mathematics can help to solve your problem only if the problem is posed in a sensible way. The initial one was, the new one isn't. Try to think a bit of what you really need. – fedja Aug 29 '13 at 11:32