BLISS: Global Blind Identification of Linear Systems with Sparse Inputs

Resumen Técnico: BLISS

1. Planteamiento del Problema

El problema central abordado es la identificación ciega de sistemas lineales invariantes en el tiempo (LTI) en un entorno totalmente observado. A diferencia de la identificación de sistemas tradicional, donde las entradas $u(k)$ son conocidas, en este escenario las entradas son desconocidas pero poseen una estructura específica: son dispersas (sparse).

Dado un sistema LTI de estado completo:
$$x(k+1) = A^\natural x(k) + B^\natural u(k)$$
donde $x(k)$ son los estados observados y $u(k)$ son las entradas desconocidas y dispersas, el objetivo es recuperar simultáneamente:

1. La matriz de dinámica del sistema $A^\natural$.
2. La matriz de entrada $B^\natural$.
3. La secuencia de entradas dispersas $U^\natural$.

Esto se formula como un problema de factorización de matrices estructuradas:
$$X^+ = A^\star X^\top + B^\star U^{\star \top}$$
donde $U^\star$ debe ser dispersa. Este problema es no convexo y, hasta ahora, carecía de garantías teóricas globales de identificación más allá de configuraciones restrictivas.

2. Metodología y Enfoque Teórico

Los autores proponen un enfoque que conecta la identificación de sistemas con el aprendizaje de diccionarios completos (Complete Dictionary Learning).

• Formulación de Maximización de Volumen:
  Inspirados en trabajos recientes sobre aprendizaje de diccionarios, los autores reformulan el problema como una maximización de volumen (o minimización de volumen del diccionario inverso) bajo restricciones de dispersión. El problema de optimización $(P)$ se define como:
  $$\min_{A,B,U} \text{vol}(B) \quad \text{sujeto a} \quad X^+ = AX^\top + BU^\top, \quad \max_i \|U_i\|_1 \leq T\mu$$
  Donde $\text{vol}(B) = \sqrt{\det(B^\top B)}$. Esta formulación actúa como un estimador de máxima verosimilitud (MLE) asumiendo que las entradas siguen una distribución Laplaciana.

• Condición de "Dispersión Persistente" (Persistent Scattering):
  Para garantizar que la solución global sea única (hasta equivalencia de escala y permutación), introducen una nueva condición geométrica llamada Dispersión Persistente. Esta es una generalización de la "suficiente dispersión" (sufficient scattering) utilizada en el aprendizaje de diccionarios.

  • Se define un zonotopo fundamental $Z$ basado en las matrices normalizadas de estados y entradas.
  • La condición requiere que este zonotopo contenga una elipse no singular y que su intersección con la frontera cumpla criterios específicos de dispersión.
  • Teorema Principal: Bajo la condición de dispersión persistente, cualquier solución óptima global $(A^\star, B^\star, U^\star)$ recupera exactamente $A^\natural$ y es equivalente a $(B^\natural, U^\natural)$ (salvo permutación y escala).

3. Contribuciones Clave

1. Formulación Unificada: Se presenta la identificación ciega de sistemas con entradas dispersas como un problema de maximización de volumen con restricciones, unificando la teoría de sistemas y el aprendizaje de diccionarios.
2. Garantías de Identificabilidad Global: Se establecen las primeras garantías teóricas globales para la recuperación exacta de sistemas LTI generales y no estructurados bajo entradas dispersas desconocidas, mediante la condición de "dispersión persistente".
3. Algoritmo BLISS: Se introduce un algoritmo basado en una versión generalizada del Método de Direcciones Alternadas de Multiplicadores (ADMM).
   • Utiliza actualizaciones de proximidad en forma cerrada para la función $-\log|\Phi|$ (relacionada con el volumen) y proyecciones sobre bolas $\ell_1$.
   • Implementa un esquema de balanceo de residuos primario-dual para ajustar dinámicamente el parámetro de penalización $\rho$, asegurando convergencia.
4. Validación Empírica: Demostración de una transición de fase clara entre el éxito y el fracaso de la recuperación, dependiendo de la longitud de la trayectoria y el nivel de dispersión de las entradas.

4. Resultados Experimentales

Los autores validaron el algoritmo BLISS mediante simulaciones numéricas con los siguientes hallazgos:

• Configuración: Sistemas con $n=100$ estados y $m=25$ entradas. Se probaron entradas con distribuciones Gaussianas y Laplacianas.
• Transición de Fase: Los resultados muestran una transición de fase nítida. La recuperación perfecta (error < 1%) se logra cuando las entradas son suficientemente dispersas y la trayectoria temporal $T$ es lo suficientemente larga. A medida que las entradas se vuelven más densas o la trayectoria más corta, el rendimiento decae abruptamente.
• Comparación:
  • El algoritmo funciona bien tanto en el escenario ciego (desconocido $A$) como en el escenario de aprendizaje de diccionarios (conocido $A$).
  • Las entradas con distribución Laplaciana (más dispersas) permiten una recuperación exitosa con trayectorias más cortas en comparación con las Gaussianas.
  • La convergencia del algoritmo es rápida cuando el parámetro inicial $\rho$ se escala adecuadamente con respecto a la norma del sistema (inicialización "oracle").

5. Significado e Impacto

Este trabajo es significativo por varias razones:

• Puente Teórico: Cierra la brecha entre la teoría de identificación de sistemas (donde la identificación ciega era un problema abierto y mal entendido) y el aprendizaje de diccionarios (donde existen fuertes garantías globales).
• Aplicabilidad Práctica: Ofrece una solución viable para escenarios donde las entradas no son medibles pero son intrínsecamente dispersas, como en:
  • Procesamiento de señales sísmicas.
  • Detección de fallos en sistemas de control.
  • Redes neuronales biológicas (activación dispersa).
  • Programación de actuadores.
• Rigor Matemático: Proporciona condiciones suficientes interpretables para la recuperación exacta, superando las limitaciones de métodos anteriores que solo ofrecían garantías locales o asintóticas.

En conclusión, BLISS demuestra que, bajo condiciones de dispersión adecuadas, es posible recuperar un sistema dinámico lineal completo y sus entradas desconocidas a partir de una sola trayectoria de datos, utilizando una optimización no convexa bien fundamentada teóricamente.