\documentclass[11pt]{article} \setlength{\oddsidemargin}{0.0truein} \setlength{\evensidemargin}{0.0truein} \setlength{\textwidth}{6.5truein} \setlength{\topmargin}{0.0truein} \setlength{\textheight}{9.0truein} \setlength{\headsep}{0.0truein} \setlength{\headheight}{0.0truein} \setlength{\topskip}{10.0pt} \setlength{\parskip}{5mm} \usepackage{url} \begin{document} \begin{center} \textbf{\textsc{STANFORD UNIVERSITY}}\\[5pt] \textbf{\textsc{DEPARTMENT OF STATISTICS}}\\[5pt] \Large{\textbf\textsc{{DEPARTMENTAL SEMINAR}}} \end{center} \begin{center} 4:15 p.m., Tuesday, July 11, 2006\\ Sequoia Hall Room 200\\ (Cookies at 3:45 in 1st Floor Lounge) \end{center} \begin{center} \textsl{ Iddo Drori}\\ Department of Statistics\\ Stanford University \end{center} \begin{center} \textbf{Fast $L_1$ Minimization} \end{center} \noindent Finding the sparsest solution to underdetermined systems of linear equations is NP-hard. Solution methods which find the $L_1$-norm are convex and computationally tractable by linear programming in cubic time. We describe iterative algorithms running in linear time which are faster than general purpose solvers by two orders of magnitude. We demonstrate the applicability of our approach to genomewide analysis of mRNA lengths, feature selection and classification in the case of observations from a small number of examples and a large number of interacting features, and multidimensional NMR spectroscopy for protein structure determination. \end{document}