Adam Florence
Research
Total Least Squares
The total least squares problem is: Given the m-by-n
matrix A and the m-vector b, find the
n-vector x which minimizes
|| [ E | e ] ||2
subject to the constraint that
( A + E ) x = b + e
According to [3, section 12.3], the solution is
computed as follows: Let M = [ A | b ] and
let v be its last right singular vector. Then
x = - v(1:n) / v(n+1)
solves the total least squares problem.
We are concerned with the case where A is a Kronecker product,
A = C kron D. In this case,
M = [ C kron D | b ]
and we need to compute the last right singular vector of M.
By exploiting the properties of the Kronecker product, we can compute
the SVD of C kron D quickly. However, the
SVD of M cannot be computed quickly, due to the augmentation of
the vector b.
Our algorithm solves the total least squares problem iteratively, and
is explained in [1, 2]. The
Matlab code is:
- TotalLS.m : Solves the total
least squares problem where the matrix is a Kronecker product.
- demo.m : Demonstrates the use of
TotalLS.m. It generates a table of flops consumed for various
problem sizes.
There is no warranty of any kind on this code or its documentation.
All code is copyrighted (c) 2000, 2001 by Adam Florence.
Our algorithm is cubic in the size of the matrices C and
D. Had the Kronecker strucutre been ignored, flops sextic in
the size of the matrices C and D would have been
required.
If you have any questions about the code, please
e-mail me.
Bibliography
- FLORENCE, ADAM G.
Computational Multilinear Algebra, Ph.D. thesis, Cornell
University, 2001.
- FLORENCE, ADAM G.
and CHARLES F. VAN
LOAN.
Least Squares Fitting with Kronecker Products,
in preparation.
- GOLUB, GENE H.
and CHARLES F. VAN
LOAN.
Matrix Computations, Third Edition,
Johns Hopkins University Press, Baltimore, 1996.
Back to my home page.
Last updated 13 August 2001.