TY - THES ID - 3257435 TI - Weighted low rank approximation : algorithms and applications AU - Schuermans, Mieke AU - Katholieke Universiteit Leuven PY - 2006 SN - 9056826840 PB - Leuven Katholieke Universiteit Leuven DB - UniCat KW - Academic collection KW - 681.3*G12 <043> KW - Approximation: chebyshev; elementary function; least squares; linear approximation; minimax approximation and algorithms; nonlinear and rational approximation; spline and piecewise polynomial approximation (Numerical analysis)--Dissertaties KW - Theses UR - https://www.unicat.be/uniCat?func=search&query=sysid:3257435 AB - Om verfijndere tendensen in gegevens te vinden, moet er nagedacht worden over belangrijke correlaties tussen steeds grotere groepen variabelen. Jammer genoeg stijgt het aantal potentiele correlaties over het algemeen exponentieel met het aantal ingevoerde variabelen. Bijgevolg worden brutekrachtmethoden onbruikbaar. De gegevens moeten dus voldoende worden vereenvoudigd. Nochtans mogen de gegevens niet te eenvoudig voorgesteld worden of, anders gezegd, informatie die essentieel is om belangrijke correlaties te kunnen achterhalen, moet weerhouden worden. Een methode die hier wereldwijd voor gebruikt wordt, is de methode waarbij de gegevens eerst in een matrix gegoten worden om vervolgens een lagere rangbenadering ervan te zoeken. De equivalentie tussen het Gewogen Lagere Rangbenaderingsprobleem (GLRB) enerzijds en het Totale Kleinste Kwadraten (TKK) probleem anderzijds wordt onderzocht. Ondanks de schijnbaar verschillende probleemformuleringen van het GLRB probleem en het TKK probleem, wordt er aangetoond dat beide methoden tot hetzelfde wiskundig kernprobleem herleid kunnen worden, namelijk het vinden van de dichtst mogelijke gewogen lagere rangbenadering waarbij de wegingsfactoren afgeleid worden uit de statistische verdelingen van de meetfouten. De verschillende oplossingsmethoden, zoals die gebruikt worden voor de GLRB problemen en de TKK problemen, worden besproken. Wij bespreken in het bijzonder de nulruimte-geparametrizeerde GLRB (NullGLRB) methode, de Maximum Likelihood Principaal Component Analyse (MLPCA), de element-gewijze gewogen TKK (EG-TKK) methode en de veralgemeende TKK (VTKK) methode. Er wordt aangetoond dat deze vier methoden een equivalent gewogen lagere rangbenaderingsprobleem aanpakken, maar dat ze verschillende algoritmen gebruiken om tot een goede benaderingsmatrix te komen. Het GLRB probleem wordt in het toepassingsgebied van de chemometrie bestudeerd. In de chemometrie worden er reeds welgekende methoden, zoals de (ML)PCA, gebruikt om een goede lagererangbenaderingsmatrix te bepalen. Het nut van TKK algoritmen voor problemen uit de chemometrie wordt besproken. Er wordt een nieuwe versie ontwikkeld van de reeds bestaande EG-TKK methode om lagere rangbenaderingsproblemen uit de chemometrie op te lossen voor matrices met meer kolommen dan rijen en waarvoor de meetfouten enkel gecorreleerd zijn binnen de rijen. Er wordt aangetoond dat dit nieuwe algoritme een goed alternatief is voor de reeds bestaande methoden die op dit moment in de chemometrie gebruikt worden. Het GLRB probleem wordt uitgebreid voor lineair gestructureerde matrices. We bestuderen de Hankel-structuur omdat deze structuur één van de meest voorkomende structuren in signaalverwerking is. Wij bestuderen de scalaire Hankel-structuur en de blok-rij Hankel-structuur. Voor beide structuren worden er nieuwe algoritmen voorgesteld om deze gestructureerde GLRB problemen op te lossen. Deze algoritmen kunnen gestructureerde GLRB problemen oplossen waarbij de rang gereduceerd kan worden met meer dan één. De meeste algoritmen uit de literatuur kunnen slechts GLRB problemen oplossen waarbij de rang slechts met eentje verlaagd wordt. Aan de hand van simulatievoorbeelden wordt er aangetoond dat de ontwikkelde algoritmen een hogere statistische nauwkeurigheid hebben dan de algoritmen uit de literatuur. Het gestructureerde GLRB probleem wordt bestudeerd om de hoekpunten van een vlakke veelhoek te kunnen reconstrueren aan de hand van zijn gegeven complexe momenten. De gestructureerde TKK methode is tot nu toe niet aan bod gekomen in de literatuur als mogelijke methode om dit reconstructieprobleem aan te pakken. Wij bespreken de mogelijkheden en beperkingen van deze alternatieve TKK oplossingsmethode in vergelijking met methoden die wel in de literatuur besproken worden om het reconstructieprobleem op te lossen. In order to find more sophisticated trends in data, potential correlations between larger and larger groups of variables must be considered. Unfortunately, the number of such correlations generally increases exponentially with the number of input variables and, as a result, brute force approaches become unfeasible. So, the data needs to be simplified sufficiently. Yet, the data may not be oversimplified. A method that is widely used for this purpose is to first cast the data as a matrix and then compute a low rank matrix approximation. The tight equivalences between the Weighted Low Rank Approximation (WLRA) problem and the Total Least Squares (TLS) problem are explored. Despite the seemingly different problem formulations of WLRA and TLS, it is shown that both methods can be reduced to the same mathematical kernel problem, i.e. finding the closest (in a certain sense) weighted low rank matrix approximation where the weight is derived from the distribution of the errors in the data. Different solution approaches, as used inWLRA and TLS, are discussed. In particular, we discuss the Null space parameterized WLRA (NullWLRA), the Maximum Likelihood Principal Component Analysis (MLPCA), the Element-wise Weighted-TLS (EW-TLS) and the Generalized TLS (GTLS) methods. It is shown that these four approaches tackle an equivalent weighted low rank approximation problem, but different algorithms are used to come up with the best approximation matrix. The WLRA problem is studied in the application field of chemometrics. In chemometrics, existing approaches to come up with the best weighted low rank matrix approximation are the well-known Principal Component Analysis (PCA) method and the MLPCA method. The use of TLS-like algorithms in chemometrics is discussed. An adapted version of the EW-TLS algorithm is developed to solve the WLRA problem for data matrices in chemometrics with more columns than rows and with only row-wise correlated measurement errors. It is shown that this new algorithm is a good alternative for the existing methods used in chemometrics. The WLRA approach is extended towards linearly structured matrices. The Hankel structure is investigated since this is one of the most frequently occurring structures in signal processing applications. We study the cases of scalar Hankel matrices and block-row Hankel matrices. For both cases, new algorithms are presented in order to solve these structured WLRA problems. These algorithms can handle structured WLRA problems with rank reductions larger than one, while most existing algorithms from the literature can only handle rank-one reduction problems. By means of simulation experiments the improved statistical accuracy of the proposed algorithms compared to known algorithms from the literature is confirmed. The structured WLRA problem is studied in the field of recovering the vertices of a planar polygon from its measured complex moments.In the literature, the use of the structured TLS approach to solve this shape-from-moments problem has not been discussed. Therefore, the potential and limitations of the structured TLS algorithm and existing algorithms to solve this reconstruction problem are discussed. Om verfijndere tendensen in gegevens te vinden, moet er nagedacht worden over belangrijke correlaties tussen steeds grotere groepen variabelen. Jammer genoeg stijgt het aantal potentiële correlaties over het algemeen exponentieel met het aantal ingevoerde variabelen. Bijgevolg worden brutekrachtmethoden onbruikbaar. De gegevens moeten dus voldoende worden vereenvoudigd. Nochtans mogen de gegevens niet te eenvoudig voorgesteld worden. Een methode die hier wereldwijd voor gebruikt wordt, is de methode waarbij de gegevens eerst in een matrix gegoten worden om vervolgens een lagererangbenadering (LRB) ervan te zoeken. De exacte definities van lagererangbenaderingsproblemen worden geformuleerd en er wordt ook een overzicht gegeven van de verschillende oplossingsmethoden die door de jaren heen gepubliceerd werden. De voor- en nadelen van de bestaande methoden worden besproken en nieuwe, verbeterde methoden worden voorgesteld. Naast het lagererangbenaderingsprobleem worden er ook uitbreidingen naar gewogen LRB (GLRB)-problemen en gestructureerd GLRB (GGLRB)-problemen geformuleerd. Tevens worden er twee toepassingsgebieden uitgewerkt waarin (G)GLRB-problemen voorkomen, namelijk in de chemometrie en bij het veelhoekreconstructieprobleem op basis van gegeven complexe momenten. ER -