1
$\begingroup$

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.

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

1 Answer 1

Reset to default
1
$\begingroup$

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).

Improve this answer
$\endgroup$
11
  • $\begingroup$ 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. $\endgroup$ Commented Aug 29, 2013 at 11:23
  • $\begingroup$ It makes no sense now: $a=b_0=0$ is an obvious answer. $\endgroup$ Commented Aug 29, 2013 at 11:27
  • $\begingroup$ Drop this obvious solution, since it is out of interest. Thanks $\endgroup$ Commented Aug 29, 2013 at 11:29
  • $\begingroup$ 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. $\endgroup$ Commented Aug 29, 2013 at 11:32
  • 1
    $\begingroup$ 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... $\endgroup$ Commented Aug 29, 2013 at 19:01

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.