Sparse regression with exact clustering

This dissertation deals with three closely related topics of the lasso in addition to supplying a comprehensive overview of the rapidly growing literature in this field. The first part aims at improving the lasso to attain smaller predictor error while simultaneously keeping the model sparsity. We propose the data-augmented weighted lasso (DAWL) to make a natural combination of the lasso and other estimators like ridge regression. We investigate the data-augmentation starting from the ridge's nature in solving the singularity problem which successfully explains the reasonability of the elastic net, and from a non-asymptotic study of the lasso's variable selection which describes the roles of different parts of the Gram matrix played in lasso estimation and selection. A robust data-dependent scaling and a 'ranged lasso' are proposed to augment both the regression matrix (nondiagonally) and the response vector. In the discussions of weights, we prove a sharp oracle inequality for the weighted lasso in the orthogonal case, and propose z-value based weights with good asymptotics. Simulations show the advantages of DAWL in test error and sparsity. The second topic is the study of a generic sparse regression problem with a customizable sparsity pattern matrix, motivated by, but not limited to, a supervised gene clustering problem in microarray data analysis. The 'clustered lasso' method is proposed with l1-type penalties on both the coefficients and their pairwise differences. Somewhat surprisingly, it shows a quite different behavior than the lasso or the fused lasso; the granted power of the l1-penalty to approximate the l0-penalty seems specious in this situation. This leads us to a theoretical study of the power and limitations, of the l1-penalty in the genera framework of sparse regression. We then discuss how to combine data-augmentation and weights to improve the naive l1-penalty. To attack the challenging computation problem in high-dimensional space, we successfully generalize an iterative algorithm for solving the lasso and develop a novel accelerated 'annealing' algorithm with theoretical justifications. It applies to any sparse regression like the fused/clustered lasso, and can handle a large design matrix as well as a large sparsity pattern matrix with apparent ease. In the third part, we discuss a class of thresholding-based iterative selection procedures (TISP) for model selection and shrinkage. People have long before noticed the weakness of the convex l1-constraint (or the soft-thresholding) in wavelets and have designed many different forms of nonconvex penalties to increase model sparsity and accuracy. But for a nonorthogonal regression matrix, there is great difficulty in both investigating the performance in theory and solving the problem in computation. TISP provides a simple and efficient way to tackle this so that we successfully borrow the rich results in the orthogonal design to solve the (nonconvexly) penalized regression for a general design matrix. Our starting point is, however, the thresholding rules rather than the penalty functions. Indeed, there is a universal connection between them. But a drawback of the latter is its non-unique form, and our way greatly facilitates the computation and the analysis. In fact, we are able to build the convergence theorem and explore the theoretical properties of the selection and the estimation via TISP nonasymptotically. More importantly, a novel Hybrid-TISP is proposed based on hard-thresholding and ridge-thresholding. It provides a fusion between the l0-penalty and the l2-penalty, and adaptively achieves the right balance between shrinkage and selection in statistical modeling. In practice, Hybrid-TISP shows superiorperformance in test-error and is parsimonious.