Skip to Main content Skip to Navigation
Master thesis

Identifiability in matrix sparse factorization

Léon Zheng 1, 2
1 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 : Matrix sparse factorization is a multilinear inverse problem where given an observed matrix Z and some sparsity constraints, one tries to recover some sparse factors for which the matrix product is equal to Z. In order to better understand how to design provably good algorithms for matrix sparse factorization, this work provides some identifiability results in the case of matrix sparse factorization with only two factors, i.e., some conditions for which the observation Z is sufficient to recover without ambiguity the pair of sparse factors (X, Y) for which XY = Z, up to unavoidable permutation and scaling ambiguities due to the nature of matrix product. In particular, this work analyzes two important problem variations: the case where one of the two factors is fixed, and the case where the support of each factor is fixed. In the first case, identifiability of the right factor when the left factor is fixed can be characterized by using linear independence of specific subsets of columns in the fixed left factor. In the second case, identifiability with a fixed pair of supports can be characterized by iterative completability, i.e., the fact that the rank 1 matrices induced by the product between one column of the left factor and one row of the right factor can be completed one by one. Characterization of identifiability in these two specific problem variations allows us to establish some important necessary conditions for identifiability in the general case, which can lead in a future work to general conditions of identifiability in matrix sparse factorization.
Document type :
Master thesis
Complete list of metadata

https://hal.inria.fr/hal-03176050
Contributor : Léon Zheng <>
Submitted on : Monday, March 22, 2021 - 10:07:03 AM
Last modification on : Tuesday, March 23, 2021 - 3:28:09 AM

File

Zheng_Internship_report.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03176050, version 1

Citation

Léon Zheng. Identifiability in matrix sparse factorization. General Mathematics [math.GM]. 2020. ⟨hal-03176050⟩

Share

Metrics

Record views

6

Files downloads

146