Advanced

Sparse Modeling Heuristics for Parameter Estimation - Applications in Statistical Signal Processing

Adalbjörnsson, Stefan Ingi LU (2014)
Abstract (Swedish)
Popular Abstract in Swedish

Den här avhandlingen studerar olika statistiska metoder för att utvinna information som ligger dold i en serie av tal eller andra symboler, exempelvis bokstäver. En sådan serie kan innehålla slumpmässighet eller ha vissa mätbara statistiska egenskaper, men har även ett inneboende mönster, vilket vi är intresserade av. Vi kallar vanligtvis sådana serier för signaler, och de kan representera till exempel data eller ljud som skickas över en telekommunikationskanal, människans DNA-kod, det som mäts genom en radar, eller en inspelning av musik. Gemensamt för dessa signaler är att man kan utforma modeller som beskriver signalens beteende, och kan på så sätt extrahera den intressanta informationen.... (More)
Popular Abstract in Swedish

Den här avhandlingen studerar olika statistiska metoder för att utvinna information som ligger dold i en serie av tal eller andra symboler, exempelvis bokstäver. En sådan serie kan innehålla slumpmässighet eller ha vissa mätbara statistiska egenskaper, men har även ett inneboende mönster, vilket vi är intresserade av. Vi kallar vanligtvis sådana serier för signaler, och de kan representera till exempel data eller ljud som skickas över en telekommunikationskanal, människans DNA-kod, det som mäts genom en radar, eller en inspelning av musik. Gemensamt för dessa signaler är att man kan utforma modeller som beskriver signalens beteende, och kan på så sätt extrahera den intressanta informationen. Denna kan man till exempel använda för att prediktera hur ännu okända delar av signalen kan bete sig, såsom i väderprognoser. Informationen kan även användas för att bevisa eller motbevisa olika hypoteser, som att avgöra huruvida ett förhöjt blodsockervärde är friskt eller ej. Avhandlingen behandlar huvudsakligen parametriska modeller, vilket innebär att den matematiska modellen innehåller parametervärden som beskriver signalens beteende. Att finna dessa parametrar, eller att skatta dem som det heter inom statistiken, är en förutsättning för att besvara de relevanta frågeställningarna. Ett exempel på en parametrisk modell är den för pianosträngen, där man vanligtvis enbart söker parametern för grundfrekvensen genom att titta på dess harmoniska frekvensinnehåll. Att därmed utelämna klang och andra musikaliska egenskaper är förstås en grov förenkling av verkligheten, men en modell utformas ofta för att endast besvara de frågeställningar man faktiskt ställt - varken mer eller mindre. I exemplet med pianosträngen kan detta motsvara att man vill veta vilka noter som spelats i en melodi, eller dess rytm. Parameteriska modeller har en lång tradition inom matematisk statistik och signalbehandling och tillämpas flitigt inom en rad olika ingenjörsområden - med goda praktiska och teoretiska resultat. Avhandlingen är avgränsad till metoder som behandlar ett vanligt förekommande problem med parametriska modeller - deras brist på flexibilitet. Detta kan illustreras till exempel genom att återgå till exemplet med pianosträngen. Vad händer om man vill finna de noter som ett piano spelar i ett musikstycke, ifall inspelningen även innehåller en violin som spelar andra noter? Om modellen inte antar att signalen består av två instrument, blir oftast resultatet helt felaktigt. Antingen så väljs den ton som spelas starkast, vilket inte nödvändigtvis är pianot, eller så väljs ett mellanting mellan de båda tonerna, vilken varken motsvarar pianot eller violinen. Denna problematik, alltså hur man skattar parametrar när man inte vet hur många komponenter som finns i signalen, är avhandlingens huvudtema. Dess olika kapitel avser olika tillämpningar, där vi skattar grundtoner i harmoniska (och nästan harmoniska) ljudsignaler, lokaliserar olika ljudkällors position, hittar dolda repetitioner i sekvenser av symboler och bestämmer parametrarna för flerdimensionella dämpade svängningar, vilka man finner inom exempelvis den medicinska tekniken. I samtliga fall beskriver modellen signalen väl, men endast under förutsättning att man vet exakt hur många komponenter den består av. Metoderna som utvecklas i avhandlingen bygger på relativt nya matematiska insikter om vilka ekvationssystem som kan lösas, specifikt när ekvationssystem har lösningar där de flesta okända variablerna är exakt lika med noll, då man säger att lösningen är gles eller ”sparse”. Detta innebär ofta att man måste göra ytterligare förenklingar för att det skall gå att lösa ekvationerna. Ett sätt att göra detta är att använda ett stort ekvationssystem där varje potentiell komponent av signalen, varje så kallad kandidat, får sin egen variabel. När de olika kandidaterna i någon mening är olika varandra, kommer en numerisk lösningsmetod att automatisk välja vilka kandidater som är lämpliga, vilket då ger antal komponenter tillsammans med kandidaternas respektive parametrar. Att uttrycka den parametriska modellen som ett ekvationssystem av kandidater kan göras på flera sätt och beroende på hur man gör kan resultaten bli väldigt olika. I avhandlingen behandlas därför detta specifikt för varje tillämpning. Genom att matematiskt analysera modellen har vi hittat strukturer som tillåter komponenterna i ekvationssystemet att vara tillräckligt olika. I de två artiklarna om att skatta grundfrekvenser i ljud och om att lokalisera ljud visar vi att man kan få bättre resultat genom att gruppera signalens komponenter i harmoniska strukturer. Detta innebär att man låter varje kandidat motsvara en sådan grupp och låta lösningsmetodiken välja lämpliga kandidater, under premissen att dessa skall vara få. Resultaten är lovande och i flera fall har vi kunnat visa att förenklingarna inte leder till sämre skattningar än då man vetat exakt antal komponenter i signalen. Eftersom den uppmätta signalen ofta genererar mycket stora datamängder har vi även utvecklat beräkningseffektiv lösningsmetodik då standardlösningarna skulle bli alldeles för tidskrävande. (Less)
Abstract
This thesis examines sparse statistical modeling on a range of applications in audio modeling, audio localizations, DNA sequencing, and spectroscopy. In the examined cases, the resulting estimation problems are computationally cumbersome, both as one often suffers from a lack of model order knowledge for this form of problems, but also due to the high dimensionality of the parameter spaces, which typically also yield optimization problems with numerous local minima.

In this thesis, these problems are treated using sparse modeling heuristics, with the resulting criteria being solved using convex relaxations, inspired from disciplined convex programming ideas, to maintain tractability. The contributions to audio modeling and... (More)
This thesis examines sparse statistical modeling on a range of applications in audio modeling, audio localizations, DNA sequencing, and spectroscopy. In the examined cases, the resulting estimation problems are computationally cumbersome, both as one often suffers from a lack of model order knowledge for this form of problems, but also due to the high dimensionality of the parameter spaces, which typically also yield optimization problems with numerous local minima.

In this thesis, these problems are treated using sparse modeling heuristics, with the resulting criteria being solved using convex relaxations, inspired from disciplined convex programming ideas, to maintain tractability. The contributions to audio modeling and estimation focus on the estimation of the fundamental frequency of harmonically related sinusoidal signals, which is commonly used model for, e.g., voiced speech or tonal audio. We examine both the problems of estimating multiple audio sources assuming the expected harmonic structure, as well as the problem of robustness to the often occurring inharmonic structure, such that the higher order sinusoidal components deviate in an unknown way from the expected multiples of the fundamental frequency. This is a problem commonly occurring for, for instance, string instruments, which, if not properly accounted for, will degrade the performance of most pitch estimators noticeably. We also consider the problem of localizing audio sources in an unknown and possibly reverberant acoustic environment, allowing for simultaneous localization of far-field and near-field signals. The DNA sequencing contribution, presented in the more general setting of arbitrary categorical sequences, is inspired by the problem of identifying segments in the genome, which are characterized by the highly periodic behavior of the sequence. In each of the contributions, an appropriate computationally efficient algorithm is proposed. Specifically for the sparse models, alternating directions method of multipliers and cyclic coordinate descent implementations are suggested, since the proposed convex criteria are in practice easier to solve than the standard interior point solvers would suggest. The suggested methods are in all cases compared with previously proposed algorithms and/or measured data, as appropriate. (Less)
Please use this url to cite or link to this publication:
author
supervisor
opponent
  • Jansson, Magnus, The Royal Institute of Technology (KTH), Stockholm, Sweden
organization
publishing date
type
Thesis
publication status
published
subject
keywords
parameter estimation, sparse models, convex optimization, fundamental frequency, inharmonicity, audio localization, symbolic periodicity, alternating directions method of multipliers, N-dimensional decaying sinusoids.
pages
179 pages
publisher
Centre for Mathematical Sciences, Lund University
defense location
Lecture hall MH:A, Centre for Mathematical Sciences, Sölvegatan 18, Lund University Faculty of Engineering
defense date
2014-10-31 13:15
ISBN
978-91-7623-107-4
language
English
LU publication?
yes
id
fd8ac862-4635-4f78-a94c-c90bc9628157 (old id 4696166)
date added to LUP
2014-10-09 10:22:16
date last changed
2016-09-19 08:45:03
@misc{fd8ac862-4635-4f78-a94c-c90bc9628157,
  abstract     = {This thesis examines sparse statistical modeling on a range of applications in audio modeling, audio localizations, DNA sequencing, and spectroscopy. In the examined cases, the resulting estimation problems are computationally cumbersome, both as one often suffers from a lack of model order knowledge for this form of problems, but also due to the high dimensionality of the parameter spaces, which typically also yield optimization problems with numerous local minima. <br/><br>
In this thesis, these problems are treated using sparse modeling heuristics, with the resulting criteria being solved using convex relaxations, inspired from disciplined convex programming ideas, to maintain tractability. The contributions to audio modeling and estimation focus on the estimation of the fundamental frequency of harmonically related sinusoidal signals, which is commonly used model for, e.g., voiced speech or tonal audio. We examine both the problems of estimating multiple audio sources assuming the expected harmonic structure, as well as the problem of robustness to the often occurring inharmonic structure, such that the higher order sinusoidal components deviate in an unknown way from the expected multiples of the fundamental frequency. This is a problem commonly occurring for, for instance, string instruments, which, if not properly accounted for, will degrade the performance of most pitch estimators noticeably. We also consider the problem of localizing audio sources in an unknown and possibly reverberant acoustic environment, allowing for simultaneous localization of far-field and near-field signals. The DNA sequencing contribution, presented in the more general setting of arbitrary categorical sequences, is inspired by the problem of identifying segments in the genome, which are characterized by the highly periodic behavior of the sequence. In each of the contributions, an appropriate computationally efficient algorithm is proposed. Specifically for the sparse models, alternating directions method of multipliers and cyclic coordinate descent implementations are suggested, since the proposed convex criteria are in practice easier to solve than the standard interior point solvers would suggest. The suggested methods are in all cases compared with previously proposed algorithms and/or measured data, as appropriate.},
  author       = {Adalbjörnsson, Stefan Ingi},
  isbn         = {978-91-7623-107-4},
  keyword      = {parameter estimation,sparse models,convex optimization,fundamental frequency,inharmonicity,audio localization,symbolic periodicity,alternating directions method of multipliers,N-dimensional decaying sinusoids.},
  language     = {eng},
  pages        = {179},
  publisher    = {ARRAY(0xbf83258)},
  title        = {Sparse Modeling Heuristics for Parameter Estimation - Applications in Statistical Signal Processing},
  year         = {2014},
}