Cómo justificar la solución de este problema?

Question

Suponga $\mathbf{x} \in \mathbb R_+^N$ con el apoyo $P=\{p_1,p_2,\cdots,p_K\}$ ($P$ se desconoce). Ya sabemos que $$f_1(\mathbf{x}) = f_2(\mathbf{x}) = \cdots = f_{N-1}(\mathbf{x})$$ donde $$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}$$

Este problema se compone de $2K$ incógnitas ($P$ y distinto de cero elementos de $\mathbf{x}$) y $N-2$ ecuaciones, por lo tanto, este es un determinado sistema de ecuaciones, y en general tiene Menos de la Plaza de la solución. Después de la evaluación de LS solución para muchos de los $(N,K)$ pares, me llegaron a estos resultados (hechos):

1. Para casi todos los casos, la solución para $P$ $P$(s) cuya Diferencia conjunto múltiple tiene varianza mínima. Donde la Diferencia conjunto múltiple de un punto se define un conjunto : $D = \{a_1,a_2,\cdots,a_{N-1}\}$ $a_d$ es el número de ocurrencias de $d = p_i-p_j \mod N, \quad i \ne j$

2. El $\mathbf{x}$ solución para todos los casos, fue una solución con cerca de cero elementos, es decir, ($x_i \approx x_j, i,j\in P$)

Esta figura muestra la LS solución para el $(N,K) = (20,7)$

Alguien le preguntó cómo he resuelto este problema. Para encontrar las mejores $P$ ($P$ conduce a menos error en LS solución) he utilizado la combinatoria de búsqueda y después de encontrar a $P$, el problema restante es un continuo de mínimos cuadrados que se pueden resolver utilizando muchos métodos de optimización, tales como el de Gauss-Newton, de Levenberg-Marquardt, ... .

Aquí es cómo $f_l(x^*)$ es distribuido por $l=0,1,\cdots,N-1$:

Mi pregunta es, cómo probar el primer hecho analíticamente o incluso intuitivamente?

Le pregunté en MO .

Answer 1

Aquí podrían ser algunos de intuición:

Si usted escribe sus condiciones, tenga en cuenta que para $\|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^{lc} \left(\sum_{i=0}^{N-1} x_i x_ {i+k\ \mathrm{mod}\ N)} \right)$

Deje $c_k = \sum_{i=0}^{N-1} x_i x_{(i+k\ \mathrm{mod}\ N)}$. A continuación, $f_l$ es constante para $l=1,\ldots,N-1$ si y sólo si la DFT de $(c_0,\ldots,c_{N-1})$ es constante (a excepción de $l=0$).

Tomando nota de que $\sum_{k=1}^{N-1} w^{lk} = -1 + \sum_{k=0}^{N-1} w^{lk} = -1$, se puede calcular que la DFT de $(b,c,\ldots,c)$$(b+(N-1)c,b-c,\ldots,b-c)$. Como la DFT es invertible, esto implica que $f_l$ es constante en $l$ si y sólo si $c_k$ es constante para $k>0$.

Creo que he arreglado hasta ahora es la más directamente relacionada con multisets. Así que ahora estamos de vuelta a la misma pregunta, pero ahora podemos estudiar $c_k$ más que el original de la DFT magnitudes.

---

Más pensamientos: Relajante el problema significa buscar completa de los vectores (no pocos) $x$. También podemos preguntar qué tipo de vectores de la $c_k$ ser constante. Me parece que hay $N$ incógnitas e $N-2$ ecuaciones, pero vamos a lanzar en $\sum_{i} x_i = 1$ (que es necesaria para la $c_k$ fórmula que escribí), y también se $\sum_{i} x_i^2 = C^2$, que es el término que falta $c_0$, y varían $C$ a ver qué soluciones aspecto. Incluso no está claro para mí lo que en esta imagen se ve, o si es pertinente. Para $C^2 = 1/N$, entonces la constante de la solución satisface la ecuación, y debe ser el único. De lo contrario, ¿quién sabe? Una vez que se entiende esto, entonces se añade la escasa restricción... supongo que lo que pasa es que un comportamiento interesante será alrededor de $C^2 \sim 1/k$ por cada nivel de dispersión $k$?