Optimización no convexa: $\min ||y-Ax||_p$ para muy pequeños $p$ dado que $||x||_2=1$

Question

Necesito encontrar $x$ que minimice la función de coste $\|y-Ax\|_p$ cuando $p$ está cerca de $0$ sujeto a la restricción $\|x\|_2=1$ donde $x$ y $y$ son vectores en $\mathbb{R}^n$ y $A$ es un $n\times n$ matriz de rango completo tal que $A^TA$ es diagonal con entradas estrictamente positivas y $\operatorname{Tr}(A^TA)=N$ . La matriz $A$ y el vector $y$ son ambos conocidos. Los elementos de $A$ están en $\mathbb{R}$ . Tenga en cuenta que $A$ no es diagonal. Específicamente (si ayuda), $A=\begin{pmatrix} B& C\\ -C& B \end{pmatrix}$ donde $B$ y $C$ son de tamaño $n/2 \times n/2$ y ambas son matrices simétricas.

El problema no es convexo. Alguna idea para resolver la expresión con $A$ como una matriz de identidad o diagonal son más que bienvenidos también

La notación $\|z\|_p$ destaca la $L_p$ norma y es $\|z\|_p=\sum|z_i|^p$ donde $z_i$ son los elementos de $z$ . Para $p<1$ , $\|\cdot\|_p$ no es una norma en la definición real de la palabra, ya que desafía la desigualdad del triángulo.

Answer 1

No estoy seguro de que podamos hacer comentarios sobre el comportamiento limitador. Pero sí podemos decir algo sobre lo que ocurre en el límite $p=0$ .

En $p=0$ se intenta minimizar el número de entradas distintas de cero en el vector $e=y-Ax$ . Así, la función objetivo toma los valores del conjunto $\{0,1,2,\dots,n\}$ . El mínimo ideal es cero, es decir, cuando $y=Ax$ y el máximo es $n$ lo que ocurre cuando ninguna de las entradas de $e$ son ceros, lo que significa que $y_i\neq [Ax]_i,~\forall i$ ( $i^{th}$ entrada). Intentaré abordarlo caso por caso.

Consideremos el caso $A=I$ . En el límite $p=0$ Usted está tratando de minimizar el $l_0$ norma (es decir, número de entradas distintas de cero) en el vector diferencia $e=y-x$ . Pero también tiene la restricción adicional de que $||x||^2_2=1$ . Si $y$ era norma unitaria, entonces $x=y$ es la solución óptima. Si no lo es, hay que poner a cero las entradas de $y$ tanto como sea posible, ya que su objetivo es disminuir el número de entradas distintas de cero. La solución obvia (aunque se me escapa una prueba rigurosa) es poner a cero todas las entradas más pequeñas (en sentido absoluto) de $y$ tales que su suma al cuadrado sea menor o igual que 1. Así, se pone a cero el máximo número de entradas distintas de cero.

Consideremos el caso $A=D$ donde $D$ es una matriz diagonal. Defina $z=Dx$ . Así que hay que reducir a cero las entradas del vector $e=y-z$ . Supongamos que todas las entradas diagonales de $D$ son distintos de cero. Ahora viene una observación importante. Para cualquier vector $r$ El $l_o$ norma de $r$ es lo mismo que $Dr$ . Así que $||y-Dx||_0=||D(D^{-1}y-x)||_0=||D^{-1}y-x||_0$ . $D^{-1}y$ es un vector conocido, y ahora se sigue el método anterior para el caso de la matriz identidad.

No es necesario leer después de esto, todavía está en desarrollo :). Acabo de garabatear mis pensamientos aquí.

Consideremos el caso $A$ es tal que $A^TA$ es diagonal. A continuación, haga la observación de que $A$ debe ser de la forma $A=UD$ donde $U$ es una matriz ortogonal y $D$ es una matriz diagonal. Defina $v=U^Ty-Dx$ Observe que $||y-UDx||_0=||U(U^Ty-Dx)||_0=||Uv||_0$ . Ahora bien, ¿cuándo se minimiza esto (si uno se olvida de las restricciones). Una posibilidad es $Uv=0$ por lo que se obtiene el mínimo como 0. Esto no es posible porque $U$ es ortogonal. ¿Cuál es la siguiente mejor respuesta, puede ||Uv|| ser tal que sólo una de las entradas de sea distinta de cero?. Ahora una interpretación de $U$ es que es una matriz ortogonal, así como una matriz de rotación y también preserva la norma.

Answer 2

El trabajo de rick chartrand(2012), "nonconvex splitting for regularized low-rank + sparse decomposition", me parece relacionado de alguna manera con tu problema. Algunos pensamientos / conjeturas: Incluso si tu problema no es convexo, podría resolverse iterativamente mediante una secuencia de problemas convexos a través de métodos de división (como se describe, por ejemplo, en "Proximal Splitting Methods in Signal Processing" de combettes). También es posible que prefiera transformar la restricción dura '||x|| = 1' en un término de penalización '+ lambda * (||x|| - 1)^2'.