Sparse Matrix Factorization

By Behnam Neyshabur, Rina Panigrahy. 2013

27 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computer Vision and Pattern Recognition

Citations in the corpus

Convergent Learning: Do different neural networks learn the same representations? (2015, background): “Many recent studies have focused on understanding deep neural networks from both a theoretical perspective (Arora et al., 2014; Neyshabur & Panigrahy, 2013; Montavon et al., 2011; Paul & Venkatasubramanian, 2014; Goodfellow et al., 2014) and from an empirical perspective (Erhan et al., 2009; Eigen…”
DeepCNF-D: Predicting Protein Order/Disorder Regions by Weighted Deep Convolutional Neural Fields (2015, methodology): “…which takes into consideration the hidden structures of the neurons; (b) a dimension reduction technique [37] which could be used to reduce the total number of neuron weights; (c) a hessian-free strategy [38] which could be applied to accelerate the calculation based on the reduced neuron space.”
The Effect of Gradient Noise on the Energy Landscape of Deep Networks (2015, background): “2.1 is motivated from Arora et al. (2013) and Neyshabur and Panigrahy (2013).”
Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations (2019, background): “Sparse matrix factorization with more than two factors has also been considered, for example in the setting where the true matrix is the product of random sparse matrices [31], or in the context of learning multi-layer sparse approximations [24, 25].”