liu.seSearch for publications in DiVA
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
A block-preconditioner for a special regularized least-squares problem
Linköpings universitet, Matematiska institutionen, Beräkningsvetenskap. Linköpings universitet, Tekniska högskolan.
Linköpings universitet, Matematiska institutionen, Beräkningsvetenskap. Linköpings universitet, Tekniska högskolan.
2007 (engelsk)Inngår i: Linear Algebra with Applications, ISSN 1070-5325, Vol. 14, nr 6, s. 469-484Artikkel i tidsskrift (Fagfellevurdert) 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.

sted, utgiver, år, opplag, sider
2007. Vol. 14, nr 6, s. 469-484
Emneord [en]
conjugate gradient, least squares, regularization
HSV kategori
Identifikatorer
URN: urn:nbn:se:liu:diva-14423DOI: 10.1002/nla.533OAI: oai:DiVA.org:liu-14423DiVA, id: diva2:23478
Tilgjengelig fra: 2007-05-02 Laget: 2007-05-02 Sist oppdatert: 2009-04-26
Inngår i avhandling
1. Algorithms for a Partially Regularized Least Squares Problem
Åpne denne publikasjonen i ny fane eller vindu >>Algorithms for a Partially Regularized Least Squares Problem
2007 (engelsk)Licentiatavhandling, med artikler (Annet vitenskapelig)
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.

sted, utgiver, år, opplag, sider
Matematiska institutionen, 2007. s. 20
Serie
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 1310
Emneord
Least squares, Regularization, Block-matrices, Conjugate gradient, QR-factorization, Cross-validation
HSV kategori
Identifikatorer
urn:nbn:se:liu:diva-8784 (URN)978-91-85831-93-7 (ISBN)
Presentation
2007-05-29, Glashuset, Hus B, Linköpings universitet, Linköping, 10:15 (engelsk)
Opponent
Veileder
Tilgjengelig fra: 2007-05-02 Laget: 2007-05-02 Sist oppdatert: 2009-05-14

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekstLink to Ph.D. Thesis

Personposter BETA

Elfving, TommySkoglund, Ingegerd

Søk i DiVA

Av forfatter/redaktør
Elfving, TommySkoglund, Ingegerd
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric

doi
urn-nbn
Totalt: 439 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf