University of Cambridge > Talks.cam > Statistics > Complexity analysis of the Lasso regularization path and an application of sparsity to isoform detection in RNA-seq data

Complexity analysis of the Lasso regularization path and an application of sparsity to isoform detection in RNA-seq data

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact .

This talk will be composed of two independent parts. In the first part, we will study an intriguing phenomenon related to the regularization path of the Lasso estimator. The regularization path of the Lasso can be shown to be piecewise linear, making it possible to “follow” and explicitly compute the entire path. We analyze this popular strategy, and prove that its worst case complexity is exponential in the number of variables. We then oppose this pessimistic result to an (optimistic) approximate analysis: We show that an approximate path with at most O(1/sqrt(ε)) linear segments can always be obtained, where every point on the path is guaranteed to be optimal up to a relative ε-duality gap.

In the second part, I will present a successful application of sparsity to the problem of isoform identification and quantification from RNA -Seq data. A gene is composed of several coding (exon) and non-coding parts (introns). Exons are combined into sequences called isoforms that encode a protein. An important but computationally challenging task consists of discovering isoforms from the expression of exons. This can be formulated as a sparse regression problem with an exponential number of features. We propose an approach based on an equivalence between the problem of isoform detection in sparse regression and the problem of path selection in a directed acyclic graphs, which can be solved efficiently using network flow algorithms.

This talk is part of the Statistics series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2019 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity