Sparse Matrix Factorization

Abstract

We investigate the problem of factorizing a matrix into several sparse matrices and propose an algorithm for this under randomness and sparsity assumptions. This problem can be viewed as a simplification of the deep learning problem where finding a factorization corresponds to finding edges in different layers and values of hidden units. We prove that under certain assumptions for a sparse linear deep network with $n$ nodes in each layer, our algorithm is able to recover the structure of the network and values of top layer hidden units for depths up to $\tilde{O}(n^{1/6})$. We further discuss the relation among sparse matrix factorization, deep learning, sparse recovery and dictionary learning.

20 pages

References in corpus (2)

• Provable Bounds for Learning Some Deep Representations
• New Algorithms for Learning Incoherent and Overcomplete Dictionaries

Cited by in corpus (8)

• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Flexible Multi-layer Sparse Approximations of Matrices and Applications
• Complete Dictionary Recovery over the Sphere
• Learning computationally efficient dictionaries and their implementation as fast transforms
• Hybrid Recommender System Based on Personal Behavior Mining
• A difference-of-convex approach for split feasibility with applications to matrix factorizations and outlier detection
• Effective Resistance-based Germination of Seed Sets for Community Detection
• Non-Convex Compressed Sensing with Training Data