  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.
