Flexible Multi-layer Sparse Approximations of Matrices and Applications

Abstract

The computational cost of many signal processing and machine learning techniques is often dominated by the cost of applying certain linear operators to high-dimensional vectors. This paper introduces an algorithm aimed at reducing the complexity of applying linear operators in high dimension by approximately factorizing the corresponding matrix into few sparse factors. The approach relies on recent advances in non-convex optimization. It is first explained and analyzed in details and then demonstrated experimentally on various problems including dictionary learning for image denoising, and the approximation of large matrices arising in inverse problems.

References in corpus (4)

• Provable Bounds for Learning Some Deep Representations
• Treelets--An adaptive multi-scale basis for sparse unordered data
• Sparse Matrix Factorization
• Learning computationally efficient dictionaries and their implementation as fast transforms

Cited by in corpus (13)

• Multi-Layer Convolutional Sparse Modeling: Pursuit and Dictionary Learning
• Advances in Distributed Graph Filtering
• Approximate fast graph Fourier transforms via multi-layer sparse approximations
• Fast Graph Fourier Transforms Based on Graph Symmetry and Bipartition
• Approximation spaces of deep neural networks
• A Flexible Optimization Framework for Regularized Matrix-Tensor Factorizations with Linear Couplings
• Recursive nearest agglomeration (ReNA): fast clustering for approximation of structured signals
• Inverse Multislice Ptychography by Layer-wise Optimisation and Sparse Matrix Decomposition
• Stable safe screening and structured dictionaries for faster L1 regularization
• Randomized linear algebra for model reduction. Part II: minimal residual methods and dictionary-based approximation
• QuicK-means: Acceleration of K-means by learning a fast transform
• Spurious Valleys, NP-hardness, and Tractability of Sparse Matrix Factorization With Fixed Support
• One Bit to Rule Them All : Binarizing the Reconstruction in 1-bit Compressive Sensing