Learning Simple Thresholded Features with Sparse Support Recovery
arXiv:1804.05515
Abstract
The thresholded feature has recently emerged as an extremely efficient, yet rough empirical approximation, of the time-consuming sparse coding inference process. Such an approximation has not yet been rigorously examined, and standard dictionaries often lead to non-optimal performance when used for computing thresholded features. In this paper, we first present two theoretical recovery guarantees for the thresholded feature to exactly recover the nonzero support of the sparse code. Motivated by them, we then formulate the Dictionary Learning for Thresholded Features (DLTF) model, which learns an optimized dictionary for applying the thresholded feature. In particular, for the norm involved, a novel proximal operator with log-linear time complexity is derived. We evaluate the performance of DLTF on a vast range of synthetic and real-data tasks, where DLTF demonstrates remarkable efficiency, effectiveness and robustness in all experiments. In addition, we briefly discuss the potential link between DLTF and deep learning building blocks.
arXiv commentAccepted by IEEE Transactions on Circuits and Systems for Video Technology (TCSVT)
References in corpus (10)
- Very Deep Convolutional Networks for Large-Scale Image Recognition
- Task-Driven Dictionary Learning
- Theoretical Linear Convergence of Unfolded ISTA and its Practical Weights and Thresholds
- k-Sparse Autoencoders
- Linear Convergence of Adaptively Iterative Thresholding Algorithms for Compressed Sensing
- An MDL framework for sparse coding and dictionary learning
- Efficient DC Algorithm for Constrained Sparse Optimization
- Optimized Projections for Compressed Sensing via Direct Mutual Coherence Minimization
- Cross-Domain Visual Recognition via Domain Adaptive Dictionary Learning
- Deep Regionlets: Blended Representation and Deep Learning for Generic Object Detection