Sparse coding is the problem of reconstructing input vectors using a linear combination of basis vectors with sparse coefficients. Sparse coding has become a popular method for extracting features representations from raw data. Finding the sparse code for a given input involves minimizing a quadratic reconstruction error with an $L_1$ penalty term. The process is often too slow for such applications as visual object recognition. We proposed two versions of a very fast algorithm that produces approximate estimates of the optimal sparse code. While our method only produces approximate solutions, it can be used to compute good visual features, and can be used to initialize exact iterative algorithms. The main idea is to train a non-linear, feed-forward predictor with a particular architecture and a fixed depth to produce the best possible approximation of the sparse code. A version of the method, which can be seen as a trainable version of Li and Osher's coordinate descent method, is shown to produce approximate solutions with 10 times less computation than Li and Osher's for the same approximation error. Unlike previous proposals for sparse code predictors, the system allows a kind of approximate ``explaining away'' to take place during inference. The resulting approximator is differentiable and can be included into globally-trainable recognition systems.
Download PDF