¿Qué algoritmos existen para la reconstrucción de un conjunto de vectores de un diccionario de cardinalidad más pequeña?

Este es un problema de aprendizaje del diccionario (base). En la formulación de su problema, no tiene ningún requisito sobre la representación, es decir, c_i.
considera esta notación:
x_i: n por 1 vector
D: n por K.
c_i: K por 1.

Ahora, si D es una matriz cuadrada (n = K), puede encontrar bases ortogonales utilizando el Análisis de componentes principales o puede encontrar bases no ortogonales utilizando uno de los algoritmos de análisis de Componentes independientes.
Si usa PCA, puede mantener esas bases correspondientes al mayor valor propio y formar una D que tenga un tamaño n por K donde K <n.
Si D no es una matriz cuadrada, puede utilizar algunos algoritmos bien conocidos para el aprendizaje de diccionarios. imponen restricciones de escasez en la representación (c_i) e intentan encontrar el mejor diccionario. Algunos de los algoritmos DL más conocidos son los siguientes:
K-SVD [1]
Método de dirección óptima [2]
Lagrange Dual Diccionario de aprendizaje. [3]

[1] Aharon, Michal, Michael Elad y Alfred Bruckstein. K-SVD: un algoritmo para diseñar diccionarios demasiado completos para una representación dispersa “. Procesamiento de señales, transacciones IEEE en 54, no. 11 (2006): 4311-4322.
[2] Engan, Kjersti, Sven Ole Aase y J. Hakon Husoy. “Método de direcciones óptimas para el diseño del marco”. In Acoustics, Speech, and Signal Processing, 1999. Actas., 1999 Conferencia Internacional IEEE , vol. 5, págs. 2443-2446. IEEE, 1999.
[3] Lee, Honglak, Alexis Battle, Rajat Raina y Andrew Y. Ng. “Algoritmos de codificación dispersos eficientes”. En Avances en sistemas de procesamiento de información neuronal , págs. 801-808. 2006

Probablemente necesite un algoritmo iterativo de dos pasos para actualizar el diccionario (D) y la representación de datos (c_i). Hay un montón de algoritmos de agrupación que puede implementar como k-means (ya que necesita que el tamaño del diccionario sea lo más pequeño posible).
Pero surge un problema interesante cuando su diccionario está demasiado completo. Consulte la detección de compresión y el escaso aprendizaje. La penalización de regularización l1 muestra su excelente desempeño en diferentes áreas como el aprendizaje profundo.