Material Detail

This video was recorded at Machine Learning Workshop, Sheffield 2004. There exist several condition numbers for the linear least squares (LS) problem minx ||Ax-b||. These range from a simple normwise measure that may overestimate the true numerical condition by several orders of magnitude, to refined sharp bounds. These different condition numbers will be compared and it will be shown that the computational implementation of the refined measures is problematic, but the simplest measure is easy to compute accurately. Examples are used to illustrate the differences between the condition numbers. The implications of these properties for the regularisation of ill-conditioned linear algebraic equations is considered and it is shown that it emphasizes the role of the prior. The LS problem occurs frequently in regression, and this operation plays the same role as the analysis stage in a filter bank. Similarly, the matrix-vector (MV) product b:=Ax is equivalent to the synthesis stage of a filter bank because it corresponds to the reconstruction of the signal from the basis functions. The final section of the talk will consider the condition numbers of the LS problem and MV product, and it will be shown that if the condition number of A is large, then these two operations cannot be simultaneously ill-conditioned, or simultaneously well-conditioned, that is, they obey an uncertainty principle.

Disciplines:

• Mathematics and Statistics  / Mathematics