9
$\begingroup$

Assume $\mathbf{x} \in \mathbb R_+^N$ with support $P=\{p_1,p_2,\cdots,p_K\}$ ($P$ is unknown). We already know that $$f_1(\mathbf{x}) = f_2(\mathbf{x}) = \cdots = f_{N-1}(\mathbf{x})$$ where $$f_l(\mathbf{x}) =\frac{ |DFT[x]|}{\sum_{i=0}^{N-1} x_i} =\frac{ |\sum_{i=0}^{N-1} x_i w^{il}|}{\sum_{i=0}^{N-1} x_i}, \qquad w:=e^{-j2\pi/N}$$

This problem is comprised of $2K$ unknowns ($P$ and non-zero elements of $\mathbf{x}$) and $N-2$ equations, therefore this is an over-determined system of equations, and generally it has Least Square solution. After evaluation of LS solution for many $(N,K)$ pairs, I reached these results (facts):

  1. For almost all cases, the solution for $P$ was $P$(s) whose Difference Multiset has minimum variance. Where Difference Multiset of a point-set is defined : $D = \{a_1,a_2,\cdots,a_{N-1}\}$ and $a_d$ is the number of occurrences of $d = p_i-p_j \mod N, \quad i \ne j$

  2. The $\mathbf{x}$ solution for all cases, was a solution with close non-zero elements, i.e. ($x_i \approx x_j, i,j\in P$)

This figure shows the LS solution for the $(N,K) = (20,7)$ enter image description here

Someone asked how I solved this problem. For finding the best $P$ ($P$ leading to least error in LS solution) I used combinatorial search and after finding $P$, the remaining problem is a continuous least square that is solvable using many optimization methods, such as Gauss-Newton, Levenberg-Marquardt, ... .

Here is how $f_l(x^*)$ is distributed for $l=0,1,\cdots,N-1$: enter image description here

My question is, how to prove the first fact analytically or even intuitively?

I asked it in MO too.

$\endgroup$
  • $\begingroup$ I am having trouble understanding your question. Apparently, you have a sparse signal in $\mathbb{R}^N$ with cardinality $K$ and whose DFT has a constant magnitude except at DC, where the value is unknown. Is that correct? Also, you say you $N-2$ equations, but I am counting $N-1$. I am also unable to understand what the "difference multiset" is. Lastly, I don't see how this is an over-determined system, since you have $N$ unknowns and $N-1$ equations. Knowing that $x$ has $K$ non-zero values does not tell you where they are, so you still have $N$ unknowns. $\endgroup$ – AnonSubmitter85 Aug 13 '13 at 23:23
  • $\begingroup$ Even though I am not quite sure what you are asking, I suspect the answer may be found in the digital uncertainty principle, which deals with the spacing of non-zero samples given a dense spectrum. $\endgroup$ – AnonSubmitter85 Aug 13 '13 at 23:29
  • $\begingroup$ @AnonSubmitter85 The answer to your first question is Yes, That's correct. The number of efficient equations is $N-2$. For example $x=y=z$ is comprised of 2 equations not 3, but the exact number of equations is not important. Difference mutliset as is defined, shows the number of occurrences of all pairwise modular differences of elements of $P$. If we break the problem to first finding $P$ which has $K$ unknowns, then finding non-zero values of $\mathbf x$, we would have $2K$ unknowns. $\endgroup$ – Mahdi Khosravi Aug 14 '13 at 5:55
  • $\begingroup$ You are going to have to expand on how you are solving this. From what I see, you are trying to find $\mathbf{x}=(x_0,x_1,\dots,x_N)$ such that $\vert \sum_i x_i e^{-jwi} \vert = A$ for $w=1,\dots,N-1$ and $0 \neq A \in \mathbb{R}$. That gives $N$ unknowns in $N-1$ nonlinear equations. You have the added information that $\mathbf{x}$ is $K$-sparse, so this may be doable, but I have to admit that I have my doubts since you have no phase information about the DFT. Regardless, describing how you are solving this problem might help others to offer insight. $\endgroup$ – AnonSubmitter85 Aug 15 '13 at 22:27
  • $\begingroup$ @AnonSubmitter85 Let's correct the typo in your comment : $\mathbf x = (x_0,\cdots,x_{N-1})$ such that $\vert \sum_i x_i e^{-j2\pi il/N } \vert = A$ for $l=1,\cdots,N-1$. Also I edited the question. $\endgroup$ – Mahdi Khosravi Aug 16 '13 at 4:05
2
+100
$\begingroup$

Here might be some intuition:

If you write out your conditions, note that for $\|x\|_1=1$, $f_l(x)^2 = \sum_{i,\ j=0}^{N-1} x_i x_j \omega^{l(i-j)} = \sum_{k=0}^{N-1} \omega^{lk} \left(\sum_{i=0}^{N-1} x_i x_{(i+k\ \mathrm{mod}\ N)} \right)$

Let $c_k = \sum_{i=0}^{N-1} x_i x_{(i+k\ \mathrm{mod}\ N)}$. Then $f_l$ is constant for $l=1,\ldots,N-1$ if and only if the DFT of $(c_0,\ldots,c_{N-1})$ is constant (except for $l=0$).

Noting that $\sum_{k=1}^{N-1} w^{lk} = -1 + \sum_{k=0}^{N-1} w^{lk} = -1$, we can compute that the DFT of $(b,c,\ldots,c)$ is $(b+(N-1)c,b-c,\ldots,b-c)$. As the DFT is invertible, this implies that $f_l$ is constant in $l$ if and only if $c_k$ is constant for $k>0$.

I think how I've arranged so far is more directly related to multisets. So now we're back to the same question, but now we can study $c_k$ rather than the original DFT magnitudes.


Some more thoughts: Relaxing the problem means looking at full vectors (non-sparse) $x$. We can also ask what kind of vectors will the $c_k$ be constant for. It seems like there are $N$ unknowns and $N-2$ equations, but let us throw in $\sum_{i} x_i = 1$ (which is required for the $c_k$ formula that I wrote), and also $\sum_{i} x_i^2 = C^2$, which is just the missing term $c_0$, and vary $C$ to see what solutions look like. It's not even clear to me what this picture looks like, or if it is relevant. For $C^2 = 1/N$, then the constant solution satisfies the equation, and should be the only one. Otherwise, who knows? Once this is understood, then adding on the sparse constraint... My guess as to what happens is that interesting behavior will occur around $C^2 \sim 1/k$ for each sparsity level $k$?

$\endgroup$
  • $\begingroup$ If someone say "maybe for a special $\mathbf x$ there is an imbalanced multiset that leads to same $f_l(\mathbf x)$ for all $l$'s", how would you reject it? $\endgroup$ – Mahdi Khosravi Aug 16 '13 at 13:45
  • $\begingroup$ Thank you for your attempts. I tried it for $(N,K) = (30,3)$ and $(N,K) = (40,4)$ and the observation was true, I think this holds for all pairs of $(N,K)$ conditions $\endgroup$ – Mahdi Khosravi Aug 18 '13 at 5:24
  • $\begingroup$ Why did you say $ -1 + \sum_{k=0}^{N-1} w^{lk} = -1$ ? Now what we are looking for is sparse vectors with nearly DC circular auto-correlation (or equivalently nearly DC modulus of Fourier transform) $\endgroup$ – Mahdi Khosravi Aug 18 '13 at 5:31
  • $\begingroup$ Because then when you plug in (0,c,c,...,c) into the DFT formula they turn into -c. Also sums of all the roots of unity is 0 using geometric series formula. $\endgroup$ – Evan Aug 18 '13 at 15:25
  • $\begingroup$ So the first thing I did was to square the magnitudes of the f_l and found that nice structure, and it found its way to the current state. I am a bit stumped now though... Trying to figure out a way to approach. can you also plot how far off from constant the example in the post is? $\endgroup$ – Evan Aug 18 '13 at 16:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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