Minimización de ||Ax|| con x dispersa, |x||=1

Question

Necesito un poco de ayuda para encontrar términos de búsqueda, palabras clave o, idealmente, incluso código que me ayude a encontrar una solución viable al siguiente problema de minimización.

$$^{min}_{\:\:x}\: |Ax|_2 \:\:s.t.\: |x|_2 = 1, $$ $$\:density(x)<<length(x)$$

Mi problema implica un gran número (~100) de tipos de datos, con un número aún mayor de puntos de datos (~ entre 500 - 2.000), que crean una verdadera matriz $A$ es decir $m \mathbb{x} n$ con $m>n$ . Para evitar el sobreajuste, busco un vector $x$ de tamaño $n$ que sólo tiene unos pocos términos distintos de cero.

He observado que los métodos de mínimos cuadrados totales podrían ser viables, pero todos los documentos que he encontrado sobre la resolución de TLS dispersos utilizan una ecuación de la forma $Ax=b$ y me preocupa que como mi $b$ es cero, esto puede causar problemas en cualquier implementación que intente.

notas sobre A: A no es disperso. A no tiene un núcleo. A es una matriz alternante de funciones continuas de lipschitz en una malla bastante fina. Cada columna de A tiene una magnitud igual a la longitud de esa columna.

Answer 1

Puedes intentar resolver el problema regularizado:

\begin{align} \min&\|Ax\|_2 + \lambda\|x\|_1\\[1mm] \text{s.t.}& \|x\|_2 = 1 \end{align}

donde $\lambda$ es un escalar no nulo. La suma del $1$ -término de la norma $\|x\|_1$ tiende a inducir la dispersión en la solución. El escalar $\lambda$ controla la importancia del término de regularización. Puede leer más sobre esto aquí - mira en la sección Regularizadores para la escasez. Si $A$ no es demasiado grande, entonces puedes comprobar lo cerca que estás de la solución óptima no dispersa $(\lambda = 0)$ calculando los valores singulares de $A$ y comparando con $\sigma_n$ .

Answer 2

¡¿Creo que no se puede dictar la escasez de una solución de un problema de minimización?!

Por ejemplo, si el problema de minimización fuera el valor absoluto máximo de $x_i$ la solución sería algo con todo $x_i$ igual a $\frac{1}{\sqrt{N}}$

A no ser que esté dispuesto a sacrificar la optimización por la escasez, entonces podría jugar con su algoritmo de optimización, por ejemplo, añadir una función de coste para los elementos no nulos en $x$ . No estoy seguro de cómo hacerlo en tu caso.