Aproximació escassa

La teoria de l'aproximació escassa (també coneguda com a representació escassa) tracta de solucions disperses per a sistemes d'equacions lineals. Les tècniques per trobar aquestes solucions i explotar-les en aplicacions han trobat un ampli ús en processament d'imatges, processament de senyals, aprenentatge automàtic, imatges mèdiques i molt més.

Descomposició escassa

Observacions sense soroll

Considereu un sistema lineal d'equacions ${\displaystyle x=D\alpha }$, on ${\displaystyle D}$ és un subdeterminat ${\displaystyle m\times p}$ matriu ${\displaystyle (m<p)}$ i ${\displaystyle x\in \mathbb {R} ^{m},\alpha \in \mathbb {R} ^{p}}$. La matriu ${\displaystyle D}$ (normalment se suposa que és de rang complet) s'anomena diccionari, i ${\displaystyle x}$ és un senyal d'interès. El problema central de representació escassa es defineix com la recerca de la representació més escassa possible ${\displaystyle \alpha }$ satisfactòria ${\displaystyle x=D\alpha }$ . A causa de la naturalesa subdeterminada de ${\displaystyle D}$, aquest sistema lineal admet en general infinitat de solucions possibles, i entre aquestes busquem la que tingui menys zeros diferents. Dit formalment, resolem

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

on ${\displaystyle \|\alpha \|_{0}=\#\{i:\alpha _{i}\neq 0,\,i=1,\ldots ,p\}}$ és el ${\displaystyle \ell _{0}}$ pseudo-norma, que compta el nombre de components diferents de zero de ${\displaystyle \alpha }$ . Se sap que aquest problema és NP-difícil amb una reducció a problemes de selecció de subconjunts NP-complets en optimització combinatòria.

Algorismes

Com ja s'ha esmentat anteriorment, hi ha diversos algorismes d'aproximació (també coneguts com a persecució) que s'han desenvolupat per abordar el problema de representació escassa:

${\displaystyle \min _{\alpha \in \mathbb {R} ^{p}}\|\alpha \|_{0}{\text{ subject to }}\|x-D\alpha \|_{2}^{2}\leq \epsilon ^{2}.}$

A continuació esmentem alguns d'aquests mètodes principals.

• La recerca de concordança és un algorisme iteratiu cobdiciós per resoldre aproximadament el problema anterior. Funciona trobant gradualment les ubicacions dels que no són zeros un per un. La idea bàsica és trobar a cada pas la columna (àtom). que es correlaciona millor amb el residu actual (inicialitzat a ), i després actualitzant aquest residu per tenir en compte el nou àtom i el seu coeficient. La recerca coincident pot escollir el mateix àtom diverses vegades.
• La recerca de concordança ortogonal és molt semblant a la recerca de concordança, amb una diferència important: en cadascun dels passos de l'algorisme, tots els coeficients diferents de zero s'actualitzen per mínims quadrats. Com a conseqüència, el residu és ortogonal als àtoms ja escollits i, per tant, un àtom no es pot escollir més d'una vegada.
• Mètodes cobdiciosos segons les etapes: les variacions millorades respecte a les anteriors són algorismes que funcionen amb avaricia alhora que afegeixen dues característiques crítiques: (i) la capacitat d'afegir grups de diferents de zero alhora (en lloc d'un no zero per ronda); i (ii) incloure un pas de poda a cada ronda en què es descarten diversos dels àtoms del suport. Els representants d'aquest enfocament són l'algoritme Subspace-Pursuit i el CoSaMP.^[1]

• La recerca de base resol una versió relaxada convexa del problema substituint el per una -norma. Tingueu en compte que això només defineix un nou objectiu, mentre que deixa oberta la qüestió de l'algorisme a utilitzar per obtenir la solució desitjada. Es consideren habitualment aquests algorismes els IRLS, LARS i els mètodes iteratius de contracció suau.^[2]
• Hi ha diversos altres mètodes per resoldre problemes de descomposició dispersos: mètode d'homotopia, descens de coordenades, llindar dur iteratiu, mètodes proximals de primer ordre, que estan relacionats amb els algorismes iteratius de contracció suau esmentats anteriorment i selector Dantzig.

Aplicacions

Les idees i els algorismes d'aproximació escasses s'han utilitzat àmpliament en processament de senyals, processament d'imatges, aprenentatge automàtic, imatges mèdiques, processament de matrius, mineria de dades i molt més. En la majoria d'aquestes aplicacions, el senyal d'interès desconegut es modela com una combinació escassa d'uns quants àtoms d'un diccionari determinat, i això s'utilitza com a regularització del problema. Aquests problemes solen anar acompanyats d'un mecanisme d'aprenentatge de diccionari que pretén encaixar ${\displaystyle D}$ per adaptar millor el model a les dades proporcionades. L'ús de models inspirats en la dispersió ha donat lloc a resultats d'última generació en un ampli conjunt d'aplicacions.^[3][4][5] Els treballs recents suggereixen que hi ha una estreta connexió entre el modelatge de representació escassa i l'aprenentatge profund.^[6]

Referències

1. Needell, D. and Tropp, J.A. Applied and Computational Harmonic Analysis, 26, 3, 2009, pàg. 301–321. arXiv: 0803.2392. DOI: 10.1016/j.acha.2008.07.002.
2. Zibulevsky, M. and Elad, M. IEEE Signal Processing Magazine, 27, 3, 2010, pàg. 76–88. Bibcode: 2010ISPM...27...76Z. DOI: 10.1109/MSP.2010.936023.
3. Baraniuk, R.G. Candes, E. Elad, M. and Ma, Y. Proceedings of the IEEE, 98, 2010, pàg. 906–909. DOI: 10.1109/JPROC.2010.2047424.
4. Elad, M. Figueiredo, M.A.T., and Ma, Y. «Còpia arxivada». Proceedings of the IEEE, 98, 2010, pàg. 972–982. Arxivat de l'original el 2018-01-17. DOI: 10.1109/JPROC.2009.2037655 [Consulta: 15 agost 2023].
5. Plumbley, M.D. Blumensath, T. Daudet, L. Gribonval, R. and Davies, M.E. Proceedings of the IEEE, 98, 2010, pàg. 995–1005. DOI: 10.1109/JPROC.2009.2030345.
6. Papyan, V. Romano, Y. and Elad, M. Journal of Machine Learning Research, 18, 2017, pàg. 1–52. arXiv: 1607.08194. Bibcode: 2016arXiv160708194P.