Accéder directement au contenu Accéder directement à la navigation

# Identifiability in Two-Layer Sparse Matrix Factorization

2 DANTE - Dynamic Networks : Temporal and Structural Capture Approach
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme, IXXI - Institut Rhône-Alpin des systèmes complexes
Abstract : Sparse matrix factorization is the problem of approximating a matrix $\mathbf{Z}$ by a product of $J$ sparse factors $\mathbf{X}^{(J)} \mathbf{X}^{(J-1)} \ldots \mathbf{X}^{(1)}$. This paper focuses on identifiability issues that appear in this problem, in view of better understanding under which sparsity constraints the problem is well-posed. We give conditions under which the problem of factorizing a matrix into \emph{two} sparse factors admits a unique solution, up to unavoidable permutation and scaling equivalences. Our general framework considers an arbitrary family of prescribed sparsity patterns, allowing us to capture more structured notions of sparsity than simply the count of nonzero entries. These conditions are shown to be related to essential uniqueness of exact matrix decomposition into a sum of rank-one matrices, with structured sparsity constraints. In particular, in the case of fixed-support sparse matrix factorization, we give a general sufficient condition for identifiability based on rank-one matrix completability, and we derive from it a completion algorithm that can verify if this sufficient condition is satisfied, and recover the entries in the two sparse factors if this is the case. A companion paper further exploits these conditions to derive identifiability properties and theoretically sound factorization methods for multi-layer sparse matrix factorization with support constraints associated to some well-known fast transforms such as the Hadamard or the Discrete Fourier Transforms.
Keywords :
Type de document :
Pré-publication, Document de travail
Domaine :

https://hal.inria.fr/hal-03362875
Contributeur : Léon Zheng Connectez-vous pour contacter le contributeur
Soumis le : mardi 16 novembre 2021 - 16:39:05
Dernière modification le : vendredi 19 novembre 2021 - 03:29:54

### Fichiers

main.pdf
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : hal-03362875, version 2
• ARXIV : 2110.01235

### Citation

Léon Zheng, Elisa Riccietti, Rémi Gribonval. Identifiability in Two-Layer Sparse Matrix Factorization. 2021. ⟨hal-03362875v2⟩

### Métriques

Consultations de la notice

## 29

Téléchargements de fichiers