Relação de Sensor comprimido com regularização L1

8

Entendo que o sensor comprimido encontra a solução mais esparsa para onde , e , .X R D Um R k x D y R k k < < D

y=Ax
xRDARk×DyRkk<<D

Dessa maneira, podemos reconstruir (o original) usando (a compressão), razoavelmente rápido. Dizemos que é a solução mais esparsa. A escassez pode ser entendida como a 0 para vetores.yxyl 0xl0

Também sabemos que a -norm (solucionável usando programação linear) é uma boa aproximação à -norm (que é NP-difícil para vetores grandes). Portanto é também a menor solução paral 0 x l 1 A x = yl1l0xl1Ax=y

Eu li que o sensor compactado é semelhante à regressão com uma penalidade de laço ( ). Também vi interpretações geométricas disso, mas não fiz a conexão matematicamente.l1

Além de minimizar a norma , qual é a relação (matematicamente) entre compressão e Lasso?l1

ilanman
fonte
relacionado: quora.com/…
Charlie Parker
para mim, o Compressed Sensing é o campo que estuda a recuperação de sinais esparsos e a regularização L1 é apenas uma formulação específica para aproximadamente resolvê-lo.
Charlie Parker

Respostas:

6

Não há essencialmente nenhuma diferença. É apenas a terminologia do estatístico versus a terminologia do engenheiro elétrico.

A detecção compactada (mais precisamente, denoising de busca de base [1]) é este problema:

arg minx12Axb+λx1

enquanto o Lasso [2] é esse problema

arg minβ12yXβ+λβ1

Na medida em que há uma diferença, é que, em aplicativos de Sensor de compressão, você (o engenheiro) escolhe para ser "bem comportado", enquanto, para o Lasso, você (o estatístico) não escolhe e precisa lidar com quaisquer que sejam os dados (e eles raramente são "legais" ...). Conseqüentemente, grande parte da literatura subsequente do Compressed Sensing se concentrou em escolher para ser o mais "eficiente" possível, enquanto grande parte da literatura estatística subsequente se concentrou em melhorias no laço que ainda funcionam com que "quebram" o laço.X A XAXAX

[1] SS Chen, DL Donoho, MA Saunders. "Decomposição atômica por busca de base". Jornal SIAM sobre Computação Científica 20 (1), p.33-61, 1998. https://doi.org/10.1137/S1064827596304010

[2] R. Tibshirani "Retração e seleção de regressão através do laço". Jornal da Sociedade Estatística Real: Série B 58 (1), p.267-88, 1996. JSTOR 2346178.

mweylandt
fonte
mas o sensor geralmente comprimido é expresso como tal que . Isso é realmente equivalente a min de se sim, por que e como o lambda se enquadra na imagem original? A x = b A x - b + λ x 1minx1Ax=bAxb+λx1
26418 Charlie ParkerMar
A formulação que você fornece (com a restrição de igualdade) é o "limite" em um sentido como . Ele surge quando você assume que não há ruído no sistema (por isso é chamado de "busca de base" em oposição a "denoising de busca de base"). λ0
mweylandt
algo que estou confuso é que, apesar de combinar métodos de busca em que algoritmos gananciosos resolvem (aproximadamente) . No entanto, pensei em algoritmos de limiar suave, em que os solucionadores exatos da formulação de relaxação convexa . Assim, se isso for verdade, eles levariam à mesma solução? isto é, parece que Lasso e OM resolvem o mesmo problema, mas com uma formulação muito diferente. Qualquer algoritmo para LASSO produz a mesma solução, porque sua configuração convexa se OM é um algoritmo ganancioso para L0, então eu assumiria que eles são muito diferentes. Isto está certo? X w - y 2 + λ w 1Xwy2+λw0Xwy2+λw1
Charlie Parker
Eu acho que vale a pena fazer isso em uma pergunta separada. Em geral, não - as soluções L1 (laço) e L0 (melhores subconjuntos) são diferentes. Mas há circunstâncias especiais bem estudadas em que as versões L0 e L1 do problema de busca de base (não o ruído da busca de base) fornecem a mesma solução.
mweylandt
1
Aqui está a outra pergunta: stats.stackexchange.com/questions/337113/…
Charlie Parker