Identifiability in Exact Multilayer Sparse Matrix Factorization

Léon Zheng (1, 2) , Rémi Gribonval (1) , Elisa Riccietti (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme
2 Valeo.ai

Many well-known matrices Z are associated to fast transforms corresponding to factorizations of the form Z = X^(L). .. X^(1) , where each factor X^(l) is sparse. Based on general result for the case with two factors, established in a companion paper, we investigate essential uniqueness of such factorizations. We show some identifiability results for the sparse factorization into two factors of the discrete Fourier Transform, discrete cosine transform or discrete sine transform matrices of size N = 2^L , when enforcing N/2-sparsity by column on the left factor, and 2-sparsity by row on the right factor. We also show that the analysis with two factors can be extended to the multilayer case, based on a hierarchical factorization method. We prove that any matrix which is the product of L factors whose supports are exactly the so-called butterfly supports, admits a unique sparse factorization into L factors. This applies in particular to the Hadamard or the discrete Fourier transform matrix of size 2^L .

Mots clés: Identifiability; Matrix factorization; Sparsity; Multilinear inverse problem; Matrix completion

Domaines: Apprentissage [cs.LG]

Léon Zheng, Rémi Gribonval, Elisa Riccietti. Identifiability in Exact Multilayer Sparse Matrix Factorization. 2021. ⟨hal-03362626v1⟩