Grundsträvan denoising

Inom tillämpad matematik och statistik hänvisar base pursuit denoising (BPDN) till ett matematiskt optimeringsproblem av formen

$\min _{x}\left({\frac {1}{2}}\|y-Ax\| _{2}^{2}+\lambda \|x\|_{1}\höger),$

där $\lambda$ är en parameter som styr avvägningen mellan sparsitet och rekonstruktionsfidelitet, $x$ är en $N\times 1$ lösningsvektor, $y$ är en $M\times 1$ vektor av observationer, $A$ är en $M\times N$ transformationsmatris och $M<N$ . Detta är ett exempel på konvex optimering och även kvadratisk programmering .

Vissa författare hänvisar till förnekande av grundsträvan som följande närbesläktade problem:

$\min _{x}\|x\|_{1}{\text{ med förbehåll för }}\|y-Ax \|_{2}^{2}\leq \delta ,$

vilket, för en given $\lambda$ , är ekvivalent med den obegränsade formuleringen för något (vanligtvis okänt a priori ) värde på $\delta$ . De två problemen är ganska lika. I praktiken föredras vanligtvis den obegränsade formuleringen, för vilken de flesta specialiserade och effektiva beräkningsalgoritmer utvecklas.

Båda typerna av denoising löser ett regulariseringsproblem med en avvägning mellan att ha en liten residual (att göra $y$ nära $Ax$ i termer av kvadratfelet) och att göra $x$ enkel i $\ell _{1}$ -normen. Det kan ses som ett matematiskt uttalande av Occams rakhyvel , där man hittar den enklaste möjliga förklaringen (dvs en som ger ${\displaystyle \min _{x}\|x\|_{1}} )$ kapabel . att redogöra för observationerna $y$ .

Exakta lösningar på denoising av grundsträvan är ofta den bästa beräkningsmässigt följbara approximationen av ett underbestämt ekvationssystem. Bassträvan denoising har potentiella tillämpningar inom statistik (se LASSO -metoden för regularisering ), bildkomprimering och komprimerad avkänning .

När $\delta =0$ blir det här problemet grundsträvan .

Basis pursuit denoising introducerades av Chen och Donoho 1994 inom området signalbehandling. I statistiken är den välkänd under namnet LASSO , efter att ha introducerats av Tibshirani 1996.

Lösande grund strävan denoising

Problemet är ett konvext kvadratiskt problem, så det kan lösas av många generella lösare, till exempel invändiga punktmetoder . För mycket stora problem har många specialiserade metoder som är snabbare än invändiga punktmetoder föreslagits.

Flera populära metoder för att lösa grundsträvan-denoising inkluderar in-crowd-algoritmen (en snabb lösare för stora, glesa problem), homotopifortsättning , fastpunktsfortsättning (ett specialfall av framåt-bakåtalgoritmen) och spektral projicerad gradient för L1-minimering (vilket faktiskt löser LASSO , ett relaterat problem).

externa länkar

• En lista över BPDN-lösare på wikin för glesa och lågrankade approximationer .