Solucionando problemas de otimização convexa usados ​​para denoising de alta qualidade

8

A resposta mais votada para esta pergunta sugere que, para minimizar um sinal, preservando transições nítidas, deve-se

minimizar a função objetivo:

|xy|2+b|f(y)|

onde é o sinal barulhento, y é o sinal denoised, b é o parâmetro de regularização e | f ( y ) | é alguma penalidade da norma L1. A remoção de denoising é realizada encontrando a solução y para esse problema de otimização eb depende do nível de ruído.xyb|f(y)|yb

No entanto, não há indicação de como se pode conseguir isso na prática, pois isso é um problema em um espaço dimensional muito alto, especialmente se o sinal tiver, por exemplo, 10 milhões de amostras. Na prática, como esse tipo de problema é resolvido computacionalmente para sinais grandes?

John Robertson
fonte
Você está preocupado com o tempo de execução? Caso contrário, a iteratura de como minimizar uma função é bastante extensa (Levenberg-Marquardt, Nelder-Mead etc.). Existem até algumas versões modificadas feitas especificamente para isso.
thang
Na verdade, tenho uma pergunta para as pessoas que estão respondendo abaixo. Além de lento, o que há de errado em algo como Levenberg-Marquardt ou Nelder-Mead? Estes são otimizadores generalizados, para que você possa aproximar numericamente . f
thang
Sim, estou preocupado com o tempo de execução, mas obrigado por apontar esses métodos.
John Robertson

Respostas:

6

Boyd tem um solucionador Matlab para problemas de mínimos quadrados Large1-regularizados em larga escala . A formulação do problema é um pouco diferente, mas o método pode ser aplicado para o problema.

A abordagem clássica de minimização de majoração também funciona bem. Isso corresponde à execução iterativa de limiar suave ( para TV, recorte ).

As soluções podem ser vistas nos links. No entanto, existem muitos métodos para minimizar esses funcionais pelo uso extensivo da literatura de otimização.

PS: Como mencionado em outros comentários, o FISTA funcionará bem. Outra família de algoritmos "muito rápidos" são os algoritmos primal-duplo. Você pode ver o artigo interessante de Chambolle, por exemplo, no entanto, existem inúmeros trabalhos de pesquisa sobre métodos primal-duplos para formulações lineares de problemas inversos.

Deniz
fonte
A que 'primal-dual' se refere exatamente?
Spacey
Mohammad, não implementei nenhum algoritmo primal-duplo para problemas inversos. No entanto, você pode ver um exemplo no link que mencionei na resposta: o artigo de Chambolle. Neste artigo, você pode ver o que significa um algoritmo primal-duplo com precisão. Esses métodos fornecem apenas outra solução (e rapidamente convergente) para problemas inversos.
Deniz #
f
1
4

Para resolver problemas de otimização com penalidade de TV, usamos um algoritmo proposto recentemente chamado Algoritmos Baseados em Gradiente Rápido para Problemas de Denoising e Deblurring de Imagem de Variação Total Restrita (FISTA) , que possui melhor taxa de convergência que os métodos iterativos convencionais, como o ASD-POCS.

chaohuang
fonte
11
É possível adicionar mais informações sobre o algoritmo, pois a única referência que você vinculou exige a compra do artigo?
Jason R
@ JasonR, é basicamente a aceleração de Nesterov do Proxoperador. Trabalho muito bom.
Royi 18/10/19
3

f(y)=y1

xy2+by1=i(xiyi)2+bi|yi|,

minimizá-lo requer minimizar cada entrada da soma:

yi^=argmin{(xiyi)2+b|yi|}

b

Portanto, neste caso, acho que você não precisa de um solucionador mais sofisticado para estimar seu sinal.

Alejandro
fonte
L1|yi||yi+1yi|
1
fff(x0,x1,...)=(x1x0,x2x1,...)
f(y)1
2

f(x)=1(x)=|xi|
Axb22+λx1
x1x2xi
xy


f(x)=1

xi=0

  1. Axb
  2. xi=0

Essa é uma forma de mínimos quadrados ponderados iterativamente , com pesos de 0 ou 1. Eu esperaria que os métodos nos artigos citados nas respostas anteriores apresentem melhores resultados; isso é simples.

f()+λg()f()λg()

denis
fonte