This paper is a survey of dictionary screening for the lasso problem. The lasso problem seeks a sparse linear combination of the columns of a dictionary to best match a given target vector. This sparse representation has proven useful in a variety of subsequent processing and decision tasks. For a given target vector, dictionary screening quickly identifies a subset of dictionary columns that will receive zero weight in a solution of the corresponding lasso problem. These columns can be removed from the dictionary prior to solving the lasso problem without impacting the optimality of the solution obtained. This has two potential advantages: it reduces the size of the dictionary, allowing the lasso problem to be solved with less resources, and it may speed up obtaining a solution. Using a geometrically intuitive framework, we provide basic insights for understanding useful lasso screening tests and their limitations. We also provide illustrative numerical studies on several datasets.

Recently, methods of screening the lasso problem have been developed that use the target vector x to quickly identify a subset of columns of the dictionary that will receive zero weight in the solution. Current classes of screening tests are based on bounding the dual lasso solution within a sphere or the intersection of a sphere and a half space. Stronger tests are possible but are more complex and incur a higher computational cost. To investigate this, we determine the optimal screening test when the dual lasso solution is bounded within the intersection of a sphere and two half spaces, and empirically investigate the trade-off that this test makes between screening power and computational efficiency. We also compare its performance both in terms of rejection power and efficiency to existing test classes. The new test always has better rejection, and for an interesting range of regularization parameters, offers better computational efficiency.

Screening for lasso problems is a means of quickly reducing the size of the dictionary needed to solve a given instance without impacting the optimality of the solution obtained. We investigate a sequential screening scheme using a selected sequence of regularization parameter values decreasing to the given target value. Using analytical and empirical means we give insight on how the values of this sequence should be chosen and show that well designed sequential screening yields significant improvement in dictionary reduction and computational efficiency for lightly regularized lasso problems.

Representing a vector as a sparse linear combination of codewords, e.g. by solving a lasso problem, lies at the heart of many machine learning and statistics applications. To improve the efficiency of solving lasso problems, we systematically investigate lasso screening, a process that quickly identifies dictionary entries that won't be used in the optimal sparse representation, and hence can be removed from the problem. We propose a general test called an R region test that unifies existing screening tests and we derive a particular instance called the dome test. This test is stronger than existing screening tests and can be executed in linear-time as a two-pass test with a memory footprint of only three codewords.

Despite the tremendous success of wavelet-based image regularization, we still lack a comprehensive understanding of the exact factor that controls edge preservation and a principled method to determine the wavelet decomposition structure for dimensions greater than 1. We address these issues from a machine learning perspective by using tree classifiers to underpin a new image regularizer that measures the complexity of an image based on the complexity of the dyadic-tree representations of its sublevel sets. By penalizing unbalanced dyadic trees less, the regularizer preserves sharp edges. The main contribution of this paper is the connection of concepts from structured dyadic-tree complexity measures, wavelet shrinkage, morphological wavelets, and smoothness regularization in Besov space into a single coherent image regularization framework. Using the new regularizer, we also provide a theoretical basis for the data-driven selection of an optimal dyadic wavelet decomposition structure. As a specific application example, we give a practical regularized image denoising algorithm that uses this regularizer and the optimal dyadic wavelet decomposition structure.

We propose a new multichannel image denoising algorithm. To exploit important inter-channel dependencies, we first use dynamic programming to learn an explicit dyadic tree representation of the common structure of the channels. Based on this dyadic tree, optimal Haar wavelet thresholding is then applied to denoise the image. In addition to the original channels, the algorithm can employ multiple derived channels to improve tree learning. Experimental results confirm that the approach improves multichannel image denoising performance both in PSNR and in edge preservation.

Learning sparse representations on data adaptive dictionaries is a state-of-the-art method for modeling data. But when the dictionary is large and the data dimension is high, it is a computationally challenging problem. We explore three aspects of the problem. First, we derive new, greatly improved screening tests that quickly identify codewords that are guaranteed to have zero weights. Second, we study the properties of random projections in the context of learning sparse representations. Finally, we develop a hierarchical framework that uses incremental random projections and screening to learn, in small stages, a hierarchically structured dictionary for sparse representations. Empirical results show that our framework can learn informative hierarchical sparse representations more efficiently.

In this paper we reveal a connection between the coefficients of the morphological wavelet transform and complexity measures of dyadic tree representations of level sets. This leads to better understanding of the edge preserving property that has been discovered in both areas. As an immediate application, we examine a depth-adaptive soft thresholding scheme on morphological wavelet coefficients in which the threshold decays geometrically as the resolution increases. A greater decay rate gives greater preference towards unbalanced trees and this can control edge enhancement in denoised signals.

We propose a two component method for denoising multidimensional signals, e.g. images. The first component uses a dynamic programing algorithm of complexity O (N log N) to find an optimal dyadic tree representation of a given multidimensional signal of N samples. The second component takes a signal with given dyadic tree representation and formulates the denoising problem for this signal as a Second Order Cone Program of size O (N). To solve the overall denoising problem, we apply these two algorithms iteratively to search for a jointly optimal denoised signal and dyadic tree representation. Experiments on images confirm that the approach yields denoised signals with improved PSNR and edge preservation.

We propose a boosting algorithm that seeks to minimize the AdaBoost exponential loss of a composite classifier using only a sparse set of base classifiers. The proposed algorithm is computationally efficient and in test examples produces composite classifiers that are sparser and generalize as well those produced by Adaboost. The algorithm can be viewed as a coordinate descent method for the l1-regularized Adaboost exponential loss function.

By adding a spatial regularization kernel to a standard loss function formulation of the boosting problem, we develop a framework for spatially informed boosting. From this regularized loss framework we derive an efficient boosting algorithm that uses additional weights/priors on the base classifiers. We prove that the proposed algorithm exhibits a ``grouping effect, which encourages the selection of all spatially local, discriminative base classifiers. The algorithms primary advantage is in applications where the trained classifier is used to identify the spatial pattern of discriminative information, e.g. the voxel selection problem in fMRI. We demonstrate the algorithms performance on various data sets.