Convex Total Least Squares
We study the total least squares (TLS) problem that generalizes least squares regression by allowing measurement errors in both dependent and independent variables. TLS is widely used in applied fields including computer vision, system identification and econometrics. The special case when all depen...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2015
|
| Online Access: | http://hdl.handle.net/1721.1/96914 https://orcid.org/0000-0003-2035-1820 |
| _version_ | 1811088071010025472 |
|---|---|
| author | Slavov, Nikolai G Malioutov, Dmitry M., 1981- |
| author2 | Massachusetts Institute of Technology. Department of Biology |
| author_facet | Massachusetts Institute of Technology. Department of Biology Slavov, Nikolai G Malioutov, Dmitry M., 1981- |
| author_sort | Slavov, Nikolai G |
| collection | MIT |
| description | We study the total least squares (TLS) problem that generalizes least squares regression by allowing measurement errors in both dependent and independent variables. TLS is widely used in applied fields including computer vision, system identification and econometrics. The special case when all dependent and independent variables have the same level of uncorrelated Gaussian noise, known as ordinary TLS, can be solved by singular value decomposition (SVD). However, SVD cannot solve many important practical TLS problems with realistic noise structure, such as having varying measurement noise, known structure on the errors, or large outliers requiring robust error-norms. To solve such problems, we develop convex relaxation approaches for a general class of structured TLS (STLS). We show both theoretically and experimentally, that while the plain nuclear norm relaxation incurs large approximation errors for STLS, the re-weighted nuclear norm approach is very effective, and achieves better accuracy on challenging STLS problems than popular non-convex solvers. We describe a fast solution based on augmented Lagrangian formulation, and apply our approach to an important class of biological problems that use population average measurements to infer cell-type and physiological-state specific expression levels that are very hard to measure directly. |
| first_indexed | 2024-09-23T13:55:48Z |
| format | Article |
| id | mit-1721.1/96914 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:55:48Z |
| publishDate | 2015 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/969142022-09-28T17:06:58Z Convex Total Least Squares Slavov, Nikolai G Malioutov, Dmitry M., 1981- Massachusetts Institute of Technology. Department of Biology Massachusetts Institute of Technology. Department of Physics Slavov, Nikolai Slavov, Nikolai We study the total least squares (TLS) problem that generalizes least squares regression by allowing measurement errors in both dependent and independent variables. TLS is widely used in applied fields including computer vision, system identification and econometrics. The special case when all dependent and independent variables have the same level of uncorrelated Gaussian noise, known as ordinary TLS, can be solved by singular value decomposition (SVD). However, SVD cannot solve many important practical TLS problems with realistic noise structure, such as having varying measurement noise, known structure on the errors, or large outliers requiring robust error-norms. To solve such problems, we develop convex relaxation approaches for a general class of structured TLS (STLS). We show both theoretically and experimentally, that while the plain nuclear norm relaxation incurs large approximation errors for STLS, the re-weighted nuclear norm approach is very effective, and achieves better accuracy on challenging STLS problems than popular non-convex solvers. We describe a fast solution based on augmented Lagrangian formulation, and apply our approach to an important class of biological problems that use population average measurements to infer cell-type and physiological-state specific expression levels that are very hard to measure directly. 2015-05-05T16:57:18Z 2015-05-05T16:57:18Z 2014-06 Article http://purl.org/eprint/type/JournalArticle 1533-7928 http://hdl.handle.net/1721.1/96914 Malioutov, Dmitry, and Nikolai Slavov. "Convex Total Least Squares." Proceedings of the 31st International Conference on Machine Learning, Beijing, China, 2014. JMLR: W&CP volume 32. https://orcid.org/0000-0003-2035-1820 en_US http://jmlr.org/proceedings/papers/v32/malioutov14.html Journal of Machine Learning Research Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Association for Computing Machinery (ACM) Slavov |
| spellingShingle | Slavov, Nikolai G Malioutov, Dmitry M., 1981- Convex Total Least Squares |
| title | Convex Total Least Squares |
| title_full | Convex Total Least Squares |
| title_fullStr | Convex Total Least Squares |
| title_full_unstemmed | Convex Total Least Squares |
| title_short | Convex Total Least Squares |
| title_sort | convex total least squares |
| url | http://hdl.handle.net/1721.1/96914 https://orcid.org/0000-0003-2035-1820 |
| work_keys_str_mv | AT slavovnikolaig convextotalleastsquares AT malioutovdmitrym1981 convextotalleastsquares |