liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Algorithms for a Partially Regularized Least Squares Problem
Linköping University, Department of Mathematics, Scientific Computing. Linköping University, The Institute of Technology.
2007 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [sv]

Vid analys av vattenprover tagna från t.ex. ett vattendrag betäms halten av olika ämnen. Dessa halter är ofta beroende av vattenföringen. Det är av intresse att ta reda på om observerade förändringar i halterna beror på naturliga variationer eller är orsakade av andra faktorer. För att undersöka detta har föreslagits en statistisk tidsseriemodell som innehåller okända parametrar. Modellen anpassas till uppmätta data vilket leder till ett underbestämt ekvationssystem. I avhandlingen studeras bl.a. olika sätt att säkerställa en unik och rimlig lösning. Grundidén är att införa vissa tilläggsvillkor på de sökta parametrarna. I den studerade modellen kan man t.ex. kräva att vissa parametrar inte varierar kraftigt med tiden men tillåter årstidsvariationer. Det görs genom att dessa parametrar i modellen regulariseras.

Detta ger upphov till ett minsta kvadratproblem med en eller två regulariseringsparametrar. I och med att inte alla ingående parametrar regulariseras får vi dessutom ett partiellt regulariserat minsta kvadratproblem. I allmänhet känner man inte värden på regulariseringsparametrarna utan problemet kan behöva lösas med flera olika värden på dessa för att få en rimlig lösning. I avhandlingen studeras hur detta problem kan lösas numeriskt med i huvudsak två olika metoder, en iterativ och en direkt metod. Dessutom studeras några sätt att bestämma lämpliga värden på regulariseringsparametrarna.

I en iterativ lösningsmetod förbättras stegvis en given begynnelseapproximation tills ett lämpligt valt stoppkriterium blir uppfyllt. Vi använder här konjugerade gradientmetoden med speciellt konstruerade prekonditionerare. Antalet iterationer som krävs för att lösa problemet utan prekonditionering och med prekonditionering jämförs både teoretiskt och praktiskt. Metoden undersöks här endast med samma värde på de två regulariseringsparametrarna.

I den direkta metoden används QR-faktorisering för att lösa minsta kvadratproblemet. Idén är att först utföra de beräkningar som kan göras oberoende av regulariseringsparametrarna samtidigt som hänsyn tas till problemets speciella struktur.

För att bestämma värden på regulariseringsparametrarna generaliseras Reinsch’s etod till fallet med två parametrar. Även generaliserad korsvalidering och en mindre beräkningstung Monte Carlo-metod undersöks.

Abstract [en]

Statistical analysis of data from rivers deals with time series which are dependent, e.g., on climatic and seasonal factors. For example, it is a well-known fact that the load of substances in rivers can be strongly dependent on the runoff. It is of interest to find out whether observed changes in riverine loads are due only to natural variation or caused by other factors. Semi-parametric models have been proposed for estimation of time-varying linear relationships between runoff and riverine loads of substances. The aim of this work is to study some numerical methods for solving the linear least squares problem which arises.

The model gives a linear system of the form A1x1 + A2x2 + n = b1. The vector n consists of identically distributed random variables all with mean zero. The unknowns, x, are split into two groups, x1 and x2. In this model, usually there are more unknowns than observations and the resulting linear system is most often consistent having an infinite number of solutions. Hence some constraint on the parameter vector x is needed. One possibility is to avoid rapid variation in, e.g., the parameters x2. This can be accomplished by regularizing using a matrix A3, which is a discretization of some norm. The problem is formulated

as a partially regularized least squares problem with one or two regularization parameters. The parameter x2 has here a two-dimensional structure. By using two different regularization parameters it is possible to regularize separately in each dimension.

We first study (for the case of one parameter only) the conjugate gradient method for solution of the problem. To improve rate of convergence blockpreconditioners of Schur complement type are suggested, analyzed and tested. Also a direct solution method based on QR decomposition is studied. The idea is to first perform operations independent of the values of the regularization parameters. Here we utilize the special block-structure of the problem. We further discuss the choice of regularization parameters and generalize in particular Reinsch’s method to the case with two parameters. Finally the cross-validation technique is treated. Here also a Monte Carlo method is used by which an approximation to the generalized cross-validation function can be computed efficiently.

Place, publisher, year, edition, pages
Matematiska institutionen , 2007. , 20 p.
Series
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 1310
Keyword [en]
Least squares, Regularization, Block-matrices, Conjugate gradient, QR-factorization, Cross-validation
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-8784ISBN: 978-91-85831-93-7 (print)OAI: oai:DiVA.org:liu-8784DiVA: diva2:23480
Presentation
2007-05-29, Glashuset, Hus B, Linköpings universitet, Linköping, 10:15 (English)
Opponent
Supervisors
Available from: 2007-05-02 Created: 2007-05-02 Last updated: 2009-05-14
List of papers
1. A block-preconditioner for a special regularized least-squares problem
Open this publication in new window or tab >>A block-preconditioner for a special regularized least-squares problem
2007 (English)In: Linear Algebra with Applications, ISSN 1070-5325, Vol. 14, no 6, 469-484 p.Article in journal (Refereed) Published
Abstract [en]

We consider a linear system of the form A1x1 + A2x2 + =b1. The vector consists of independent and identically distributed random variables all with mean zero. The unknowns are split into two groups x1 and x2. It is assumed that AA1 has full rank and is easy to invert. In this model, usually there are more unknowns than observations and the resulting linear system is most often consistent having an infinite number of solutions. Hence, some constraint on the parameter vector x is needed. One possibility is to avoid rapid variation in, e.g. the parameters x2. This can be accomplished by regularizing using a matrix A3, which is a discretization of some norm (e.g. a Sobolev space norm). We formulate the problem as a partially regularized least-squares problem and use the conjugate gradient method for its solution. Using the special structure of the problem we suggest and analyse block-preconditioners of Schur compliment type. We demonstrate their effectiveness in some numerical tests. The test examples are taken from an application in modelling of substance transport in rivers.

Keyword
conjugate gradient, least squares, regularization
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-14423 (URN)10.1002/nla.533 (DOI)
Available from: 2007-05-02 Created: 2007-05-02 Last updated: 2009-04-26
2. A direct method for a special regularized least squares problem
Open this publication in new window or tab >>A direct method for a special regularized least squares problem
Manuscript (Other academic)
Identifiers
urn:nbn:se:liu:diva-14424 (URN)
Available from: 2007-05-02 Created: 2007-05-02 Last updated: 2010-01-13

Open Access in DiVA

fulltext(329 kB)1076 downloads
File information
File name FULLTEXT01.pdfFile size 329 kBChecksum SHA-1
38754c4d961ace347b9882813f1ccc4cdc432ac32f7dbf38722055995377444a6747e0d7
Type fulltextMimetype application/pdf

Authority records BETA

Skoglund, Ingegerd

Search in DiVA

By author/editor
Skoglund, Ingegerd
By organisation
Scientific ComputingThe Institute of Technology
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 1076 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 803 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf