Resumen Técnico: Problemas de Cercanía de Matrices Generalizadas II

Definición del Problema

Este artículo extiende el estudio de los problemas de cercanía de matrices generalizadas, abordados originalmente en [13]. El problema fundamental busca una matriz $X$ que minimice la distancia a una matriz dada $A$ bajo restricciones específicas. La forma generalizada considerada aquí involucra tres matrices dadas $A, B, C$ y minimiza la función objetivo:
$$\min_{X \in S} \|A - BXC\|$$
donde $S$ representa un conjunto factible definido por diversas restricciones (por ejemplo, rango, norma, simetría, estructura, positividad). El artículo investiga específicamente tres extensiones a la formulación estándar de la norma de Frobenius ($\|\cdot\|_F$) encontrada en [13]:

1. Términos Afines: Incorporar términos afines como $dx^TE$ o $Dxe^T$ en la función objetivo.
2. Productos de Kronecker: Reemplazar los productos matriciales estándar con productos de Kronecker (por ejemplo, $B \otimes X \otimes C$) y generalizar las restricciones de rango al rango de Kronecker.
3. Normas de Schatten: Generalizar la norma de Frobenius a normas invariantes ortogonalmente arbitrarias, específicamente las normas $p$-de Schatten ($\|\cdot\|_{\sigma,p}$).

Metodología

El artículo emplea un enfoque dual: derivar soluciones de forma cerrada para casos específicos y desarrollar un algoritmo iterativo de orden cero para el caso general.

1. Soluciones de Forma Cerrada

Los autores identifican cuatro variantes específicas del problema que admiten soluciones de forma cerrada, extendiendo los resultados de [13]:

• Cercanía Generalizada Afín: Problemas que involucran términos como $\|A - BXC + Dxe^T\|_F$. Estos se transforman en problemas de cercanía generalizada estándar utilizando operadores de proyección (Proposición 3.2).
• Producto de Kronecker Separable: Minimizar $\|A - B \otimes X \otimes C\|_F$. Esto se resuelve introduciendo un operador de reordenamiento $R$ que transforma la estructura de Kronecker en un problema estándar de cercanía de matrices (Proposición 3.3).
• Rango de Kronecker Generalizado: Minimizar $\|A - (B_1 \otimes B_2)X(C_1 \otimes C_2)\|_F$ sujeto a $\text{rank}_\otimes(X) \le r$. Esto se reduce a un problema estándar con restricción de rango mediante el operador de reordenamiento y las propiedades de la descomposición en valores singulares (SVD) de los productos de Kronecker (Proposición 3.4, Algoritmo 1).
• Trazas Parciales Prescritas: Minimizar $\|A - (B_1 \otimes B_2)X(C_1 \otimes C_2)\|_F$ sujeto a una restricción de traza parcial $\text{tr}_P(X(W \otimes I)) = \lambda W$. Esto se reduce a un problema de valores propios prescritos o a un problema con restricción de rango (Proposición 3.5, Corolario 3.6).

2. No Existencia de Resultados de Tipo Mirsky

El artículo investiga si el teorema de Eckart–Young–Mirsky (que establece que la mejor aproximación de rango-$r$ es independiente de la norma invariante ortogonalmente utilizada) se extiende al problema generalizado $\min_{\text{rank}(X) \le r} \|A - BXC\|$.

• Resultado: Los autores demuestran que no se cumple ningún resultado de tipo Mirsky cuando $B$ y $C$ no son matrices identidad.
• Evidencia: Mediante un contraejemplo (Ejemplo 4.2), demuestran que el minimizador para el problema generalizado con restricción de rango depende de la norma de Schatten específica ($p=1, 2, \infty$) elegida. Esto contrasta con el problema estándar de aproximación de rango, donde la solución es universal en todas las normas invariantes ortogonalmente.

3. Algoritmo Iterativo (Algoritmo 3)

Para los casos donde no existen soluciones de forma cerrada (específicamente para normas de Schatten generales y restricciones complejas), los autores proponen un algoritmo iterativo basado en el método de proyección de Dykstra (Algoritmo 2), especializado para normas de Schatten (Algoritmo 3).

• Mecanismo: El algoritmo alterna entre dos pasos:
  1. Actualización de $X$: Resuelve un problema de cercanía de matrices generalizado en la norma de Frobenius (utilizando métodos de [13] o las soluciones de forma cerrada derivadas en la Sección 3).
  2. Actualización de $Y$: Resuelve un problema de operador proximal para la norma de Schatten $\|Y\|_{\sigma,p} + \frac{\mu}{2}\|Y - M\|_F^2$. Los autores derivan actualizaciones explícitas de forma cerrada para los valores singulares de $Y$ para $p=1$ (norma nuclear), $p=\infty$ (norma espectral) y $p \in (1, \infty)$ general (Lemmas 5.5–5.7).
• Característica Clave: El algoritmo es de orden cero; no calcula gradientes o subgradientes explícitos. Se basa puramente en operaciones de álgebra lineal numérica (SVDs y multiplicaciones de matrices).
• Convergencia: Se demuestra que el algoritmo converge a un minimizador global desde cualquier punto inicial. La tasa de convergencia es sublineal (debido a la falta de convexidad fuerte en las normas de Schatten para $p \neq 2$), aunque los experimentos numéricos sugieren un comportamiento casi lineal en la práctica.

Resultados Clave

• Expansiones de Forma Cerrada: El artículo proporciona soluciones explícitas para las variantes afines, de producto de Kronecker separable, de rango de Kronecker y de traza parcial del problema de cercanía generalizada.
• Limitación Teórica: Establece que la universalidad de la solución a través de diferentes normas invariantes ortogonalmente (teorema de Mirsky) se rompe en presencia de multiplicadores no identidad $B$ y $C$.
• Rendimiento Algorítmico:
  • Velocidad: En experimentos numéricos (Sección 6), el Algoritmo 3 supera significativamente a los solucionadores de optimización convexa de propósito general (específicamente CVX con el solucionador SCS). Para dimensiones grandes, CVX a menudo falla en converger dentro de límites de tiempo razonables, mientras que el Algoritmo 3 converge rápidamente.
  • Precisión: El Algoritmo 3 alcanza precisión de máquina ($\approx 10^{-15}$) en el error hacia adelante, mientras que CVX exhibe errores fluctuantes (oscilando entre $10^{-7}$ y $10^3$) y a menudo falla en satisfacer restricciones (por ejemplo, en tareas de identificación de sistemas).
  • Versatilidad: El algoritmo maneja con éxito objetivos convexos no estándar (por ejemplo, norma $3/2$ de Schatten) y restricciones no convexas (por ejemplo, restricciones de rango, valores propios prescritos) que son inaccesibles para solucionadores estándar como CVX.

Significado y Afirmaciones

El artículo afirma avanzar en el campo de los problemas de cercanía de matrices mediante:

1. Extensión de la Solubilidad: Proporcionar soluciones de forma cerrada para nuevas clases de problemas que involucran términos afines y estructuras de Kronecker.
2. Clarificación de Límites Teóricos: Demostrar las limitaciones de extender teoremas de aproximación clásicos (Mirsky) a entornos generalizados.
3. Ofrecimiento de una Alternativa Robusta: Proponer un algoritmo iterativo que es globalmente convergente, libre de gradientes y computacionalmente superior a los solucionadores de propósito general.
4. Destacando la Explotación Estructural: Los autores enfatizan que explotar estructuras matriciales específicas mediante álgebra lineal numérica (como se hizo en [13] y en este trabajo) produce un mejor rendimiento y una aplicabilidad más amplia (incluyendo casos no convexos) que depender exclusivamente de marcos de optimización convexa general.

El trabajo se presenta como una secuela de [13], manteniendo la filosofía de resolver problemas de optimización sin cálculos de derivadas, aprovechando así la rica estructura de los espacios matriciales.