Convex Total Least Squares

We study the total least squares (TLS) prob-lem that generalizes least squares regression by allowing measurement errors in both de-pendent and independent variables. TLS is widely used in applied fields including com-puter vision, system identification and econo-metrics. 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 re-quiring robust error-norms. To solve such problems, we develop convex relaxation ap-proaches for a general class of structured TLS (STLS). We show both theoretically and experimentally, that while the plain nu-clear norm relaxation incurs large approxi-mation errors for STLS, the re-weighted nu-clear 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 aug-mented Lagrangian formulation, and apply our approach to an important class of bi-ological problems that use population av-erage measurements to infer cell-type and physiological-state specific expression levels that are very hard to measure directly