Simulation-based approximate solution of large-scale linear least squares problems and applications

We consider linear least squares problems, or linear systems that can be formulated into least squares problems, of very large dimension, such as those arising for example in dynamic programming (DP) and inverse problems. We introduce an associated approximate problem, within a subspace spanned by a relatively small number of basis functions, and solution methods that use simulation, importance sampling, and low-dimensional calculations. The main components of this methodology are a regression/ regularization approach that can deal with nearly singular problems, and an importance sampling design approach that exploits existing continuity structures in the underlying models, and allows the solution of very large problems. We also investigate the use of our regression/regularization approach in temporal difference-type methods in the context of approximate DP. Finally we demonstrate the application of our methodology in a series of practical large-scale examples arising from Fredholm integral equations of the first kind.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2010

Author dc:creator

• Wang, Mengdi

Advisor dc:contributor.advisor

• Dimitri P. Bertsekas.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/58388

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/58388