Condition numbers, regularisation and uncertainty principles of linear algebraic equations

author: Joab Winkler, Department of Molecular Biology and Biotechnology, University of Sheffield
published: Feb. 25, 2007,   recorded: September 2004,   views: 4120

Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


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.

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Reviews and comments:

Comment1 Ravi Sastry, March 13, 2008 at 4:21 a.m.:

Can u post the slides of this talk. ??

Write your own review or comment:

make sure you have javascript enabled or clear this field: