Estimating sparse models from multivariate discrete data via transformed Lasso

The type of l(1) norm regularization used in Lasso and related methods typically yields sparse parameter estimates where most of the estimates are equal to zero. We study a class of estimators obtained by applying a linear transformation on the parameter vector before evaluating the l(1) norm. The resulting "transformed Lasso" yields estimates that are "smooth" in a way that depends on the applied transformation. The optimization problem is convex and can be solved efficiently using existing tools. We present two examples: the Haar transform which corresponds to variable length Markov chain (context-tree) models, and the Walsh-Hadamard transform which corresponds to linear combinations of XOR (parity) functions of binary input features.