Aproximação esparsa - Sparse approximation

A teoria da aproximação esparsa (também conhecida como representação esparsa ) lida com soluções esparsas para sistemas de equações lineares . As técnicas para encontrar essas soluções e explorá-las em aplicativos têm amplo uso em processamento de imagens , processamento de sinais , aprendizado de máquina , imagens médicas e muito mais.

Decomposição esparsa

Observações silenciosas

Considere um sistema linear de equações , onde é uma matriz subdeterminada e . A matriz (normalmente considerada como full-rank) é chamada de dicionário e é um sinal de interesse. O problema central da representação esparsa é definido como a busca pela representação mais esparsa possível que satisfaça . Devido à natureza subdeterminada de , este sistema linear admite em geral um número infinito de soluções possíveis, e entre estas procuramos aquela com o menor número de não zeros. Colocado formalmente, nós resolvemos ${\ displaystyle x = D \ alpha}$${\ displaystyle D}$ ${\ displaystyle m \ times p}$ ${\ displaystyle (m <p)}$${\ displaystyle x \ in \ mathbb {R} ^ {m}, \ alpha \ in \ mathbb {R} ^ {p}}$${\ displaystyle D}$${\ displaystyle x}$${\ displaystyle \ alpha}$${\ displaystyle x = D \ alpha}$${\ displaystyle D}$

${\ displaystyle \ min _ {\ alpha \ in \ mathbb {R} ^ {p}} \ | \ alpha \ | _ {0} {\ text {sujeito a}} x = D \ alpha,}$

onde está a pseudo-norma, que conta o número de componentes diferentes de zero de . Este problema é conhecido por ser NP-difícil com uma redução para problemas de seleção de subconjunto NP-completo em otimização combinatória . ${\ displaystyle \ | \ alpha \ | _ {0} = \ # \ {i: \ alpha _ {i} \ neq 0, \, i = 1, \ ldots, p \}}$${\ displaystyle \ ell _ {0}}$${\ displaystyle \ alpha}$

A dispersão de implica que apenas alguns ( ) componentes nele são diferentes de zero. A motivação subjacente para tal decomposição esparsa é o desejo de fornecer a explicação mais simples possível de uma combinação linear do menor número possível de colunas , também conhecida como átomos. Como tal, o sinal pode ser visto como uma molécula composta de alguns elementos fundamentais retirados . ${\ displaystyle \ alpha}$${\ displaystyle k \ ll m <p}$${\ displaystyle x}$${\ displaystyle D}$${\ displaystyle x}$${\ displaystyle D}$

Embora o problema colocado acima seja de fato NP-Difícil, sua solução pode freqüentemente ser encontrada usando algoritmos de aproximação. Uma dessas opções é um relaxamento convexo do problema, obtido usando a norma -n em vez de , onde simplesmente soma os valores absolutos das entradas em . Isso é conhecido como algoritmo de busca de base (BP), que pode ser tratado usando qualquer solucionador de programação linear . Um método de aproximação alternativo é uma técnica gananciosa, como a busca de correspondência (MP), que encontra a localização dos não zeros um de cada vez. ${\ displaystyle \ ell _ {1}}$${\ displaystyle \ ell _ {0}}$${\ displaystyle \ | \ alpha \ | _ {1}}$${\ displaystyle \ alpha}$

Surpreendentemente, sob condições moderadas (usando a faísca (matemática) , a coerência mútua ou a propriedade de isometria restrita ) e o nível de esparsidade na solução , o problema de representação esparsa pode ser mostrado como tendo uma solução única, e BP e MP têm a garantia de encontrá-lo perfeitamente. ${\ displaystyle D}$${\ displaystyle k}$

Observações ruidosas

Freqüentemente, o sinal observado é ruidoso. Ao relaxar a restrição de igualdade e impor uma norma ao termo de ajuste de dados, o problema de decomposição esparsa torna-se ${\ displaystyle x}$${\ displaystyle \ ell _ {2}}$

${\ displaystyle \ min _ {\ alpha \ in \ mathbb {R} ^ {p}} \ | \ alpha \ | _ {0} {\ text {sujeito a}} \ | xD \ alpha \ | _ {2} ^ {2} \ leq \ epsilon ^ {2},}$

ou colocado em uma forma Lagrangiana,

${\ displaystyle \ min _ {\ alpha \ in \ mathbb {R} ^ {p}} \ lambda \ | \ alpha \ | _ {0} + {\ frac {1} {2}} \ | xD \ alpha \ | _ {2} ^ {2},}$

onde está substituindo o . ${\ displaystyle \ lambda}$${\ displaystyle \ epsilon}$

Assim como no caso sem ruído, esses dois problemas são NP-Difícil em geral, mas podem ser aproximados usando algoritmos de perseguição. Mais especificamente, mudando para uma norma, obtemos ${\ displaystyle \ ell _ {0}}$${\ displaystyle \ ell _ {1}}$

${\ displaystyle \ min _ {\ alpha \ in \ mathbb {R} ^ {p}} \ lambda \ | \ alpha \ | _ {1} + {\ frac {1} {2}} \ | xD \ alpha \ | _ {2} ^ {2},}$

que é conhecido como a eliminação de ruído da busca de base . Da mesma forma, a busca de correspondência pode ser usada para aproximar a solução dos problemas acima, encontrando as localizações dos não-zeros, um de cada vez, até que o limite de erro seja atingido. Aqui também, as garantias teóricas sugerem que BP e MP levam a soluções quase ótimas, dependendo das propriedades e da cardinalidade da solução . Outro resultado teórico interessante refere-se ao caso em que é unitário. Sob esta suposição, os problemas colocados acima (com ou ) admitem soluções de forma fechada na forma de retração não linear. ${\ displaystyle D}$${\ displaystyle k}$${\ displaystyle D}$${\ displaystyle \ ell _ {0}}$${\ displaystyle \ ell _ {1}}$

Variações

Existem várias variações para o problema básico de aproximação esparsa.

Esparsidade estruturada : Na versão original do problema, qualquer um dos átomos do dicionário pode ser selecionado. No modelo de esparsidade estruturado (bloco), em vez de selecionar átomos individualmente, grupos deles devem ser selecionados. Esses grupos podem ser sobrepostos e de tamanhos variados. O objetivo é representar de forma esparsa, ao mesmo tempo em que força essa estrutura de bloco. ${\ displaystyle x}$

Codificação esparsa colaborativa (conjunta) : A versão original do problema é definida para um único sinal . No modelo de codificação esparsa colaborativa (conjunta), um conjunto de sinais está disponível, cada um considerado emergir (quase) do mesmo conjunto de átomos . Nesse caso, a tarefa de busca visa recuperar um conjunto de representações esparsas que melhor descrevem os dados, ao mesmo tempo que os força a compartilhar o mesmo (ou próximo) suporte. ${\ displaystyle x}$${\ displaystyle D}$

Outras estruturas : Mais amplamente, o problema de aproximação esparsa pode ser lançado ao forçar uma estrutura desejada específica no padrão de localizações diferentes de zero em . Dois casos de interesse que foram amplamente estudados são a estrutura baseada em árvore e, mais geralmente, um suporte distribuído de Boltzmann. ${\ displaystyle \ alpha}$

Algoritmos

Como já mencionado acima, existem vários algoritmos de aproximação (também chamados de busca ) que foram desenvolvidos para abordar o problema de representação esparsa:

${\ displaystyle \ min _ {\ alpha \ in \ mathbb {R} ^ {p}} \ | \ alpha \ | _ {0} {\ text {sujeito a}} \ | xD \ alpha \ | _ {2} ^ {2} \ leq \ epsilon ^ {2}.}$

Mencionamos a seguir alguns desses métodos principais.

• A busca de correspondência é um algoritmo iterativo ganancioso para resolver aproximadamente o problema acima. Ele funciona encontrando gradualmente as localizações dos não-zeros um de cada vez. A ideia central é encontrar em cada etapa a coluna (átomo) que melhor se correlaciona com o residual atual (inicializado em ), e então atualizar esse residual para levar em consideração o novo átomo e seu coeficiente. A busca de correspondência pode escolher o mesmo átomo várias vezes.${\ displaystyle \ alpha}$${\ displaystyle D}$${\ displaystyle x}$
• A busca de correspondência ortogonal é muito semelhante à busca de correspondência, com uma grande diferença: em cada etapa do algoritmo, todos os coeficientes diferentes de zero são atualizados por mínimos quadrados . Como consequência, o resíduo é ortogonal aos átomos já escolhidos e, portanto, um átomo não pode ser escolhido mais de uma vez.
• Métodos gananciosos em fases: Variações aprimoradas em relação aos acima são algoritmos que operam avidamente enquanto adicionam dois recursos críticos: (i) a capacidade de adicionar grupos de não zeros por vez (em vez de um diferente de zero por rodada); e (ii) incluir uma etapa de poda em cada rodada em que vários dos átomos são descartados do suporte. Representantes dessa abordagem são o algoritmo Subspace-Pursuit e o CoSaMP.

• A busca de base resolve uma versão relaxada convexa do problema substituindo a norma por uma norma. Observe que isso apenas define um novo objetivo, embora deixe em aberto a questão do algoritmo a ser usado para obter a solução desejada. Normalmente considerados esses algoritmos são os métodos IRLS , LARS e métodos iterativos de redução suave.${\ displaystyle \ ell _ {0}}$${\ displaystyle \ ell _ {1}}$

• Existem vários outros métodos para resolver problemas de decomposição esparsa: método de homotopia, descida de coordenada , limite rígido iterativo, métodos proximais de primeira ordem , que estão relacionados aos algoritmos de redução suave iterativos mencionados acima e seletor de Dantzig.

Formulários

Algoritmos e ideias de aproximação esparsas têm sido amplamente usados ​​em processamento de sinal , processamento de imagem , aprendizado de máquina , imagem médica , processamento de array , mineração de dados e muito mais. Na maioria dessas aplicações, o sinal desconhecido de interesse é modelado como uma combinação esparsa de alguns átomos de um determinado dicionário, e isso é usado como regularização do problema. Esses problemas são normalmente acompanhados por um mecanismo de aprendizagem de dicionário que visa ajustar a melhor correspondência do modelo aos dados fornecidos. O uso de modelos inspirados na dispersão levou a resultados de última geração em um amplo conjunto de aplicações. Trabalhos recentes sugerem que há uma conexão estreita entre modelagem de representação esparsa e aprendizado profundo. ${\ displaystyle D}$

Veja também

• Sensoriamento comprimido
• Aprendizagem de dicionário esparsa
• K-SVD
• Lasso (estatísticas)
• Regularização (matemática) e problemas inversos

Referências