MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
"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).

share|cite|improve this answer
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
Drop this obvious solution, since it is out of interest. Thanks – Mahdi Khosravi Aug 29 '13 at 11:29
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
Not sure I can follow it as it is written :(. What is given? What can be changed? What are the exact constraints? What is the objective function? If anyone (whether the OP or not) can clearly answer these 4 questions, I'm ready to give it a serious thought. Right now I'm just a bit confused... – fedja Aug 29 '13 at 19:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.