The 2-codeword screening test for lasso problems

Solving a lasso problem is a practical approach for acquiring a sparse representation of a signal with respect to a given dictionary. Driven by the demand for sparse representations over large-scale data in machine learning and statistics, we explore lasso screening tests. These enhance solution efficiency via the elimination of codewords absent in the optimal solution prior to detailed computation. On basis of the concept of a region test and the recently introduced dome test, we propose the 2-codeword test, which uses two codewords together in a correlation screening test. In addition to the rejection rate as the performance measure, we introduce an innovative way to access the performance of a screening test, called the uncertainty measure, via a comparison with the optimal test. © 2013 IEEE