An ADMM Algorithm for a Class of Total Variation Regularized Estimation Problems
2012 (English)In: Preprints of the 16th IFAC Symposium on System Identification / [ed] Kinnaert, Michel, 2012, 83-88 p.Conference paper, Presentation (Refereed)
We present an alternating augmented Lagrangian method for convex optimization problems where the cost function is the sum of two terms, one that is separable in the variable blocks, and a second that is separable in the difference between consecutive variable blocks. Examples of such problems include Fused Lasso estimation, total variation denoising, and multi-period portfolio optimization with transaction costs. In each iteration of our method, the first step involves separately optimizing over each variable block, which can be carried out in parallel. The second step is not separable in the variables, but can be carried out very efficiently. We apply the algorithm to segmentation of data based on changes in mean (l_1 mean filtering) or changes in variance (l_1 variance filtering). In a numerical example, we show that our implementation is around 10000 times faster compared with the generic optimization solver SDPT3.
Place, publisher, year, edition, pages
2012. 83-88 p.
Machine Learning and Data Mining; Maximum Likelihood Methods; Time Series
IdentifiersURN: urn:nbn:se:kth:diva-101909DOI: 10.3182/20120711-3-BE-2027.00310ScopusID: 2-s2.0-84867091929OAI: oai:DiVA.org:kth-101909DiVA: diva2:549832
16th IFAC Symposium on System Identification, Square - Brussels Meeting Centre, Belgium
FunderICT - The Next Generation
QC 201211122012-11-122012-09-052013-09-05Bibliographically approved