4.3 Confronto dei metodi
4.3.4 Tempi di esecuzione
Abbiamo misurato i tempi di esecuzione dei tre algoritmi al variare del numero di righe m della matrice A e del numero di componenti non nulle della soluzione esatta x∗, generando problemi opportuni nella forma (2.2). Per il primo test abbiamo generato matrici A con 1000 colonne e soluzioni con kx∗k0 = 50, facendo variare il numero
4.3. Confronto dei metodi 100 200 300 400 500 600 700 800 900 1000 numero di righe m 100 200 300 400 500 600 700 800 900 1000 nnz(x*) 0 10 20 30 40 50 60 70 80 90 100
Figura 4.2: Rappresentazione grafica delle percentuali di recupero del metodo di omotopia, A con N = 1000 righe. Il colore nero corrisponde al 100% di soluzioni recuperate, il bianco allo 0%.
di righe di A da 400 a 900. Per il secondo test abbiamo fissato le dimensioni di A, generando sempre matrici con 750 righe e 1000 colonne, e abbiamo fatto variare il numero di componenti non nulle della soluzione esatta x∗ da 50 a 250. Queste scelte sono state calibrate in modo da garantire il recupero della soluzione sparsa, come descritto precedentemente. Abbiamo riassunto i risultati del primo test (al variare di m) nella figura 4.3, quelli del secondo test (al variare di k) nella figura 4.4.
Possiamo osservare come il metodo pdNCG e il metodo del punto interno rallentino in modo evidente al crescere del numero di righe della matrice del sistema. Questi due metodi infatti risolvono ad ogni passo un sistema di dimensione N × N : la matrice di tale sistema dipende dal termine ATA, il cui calcolo costa progressivamente di più al crescere di m. Al contrario, il metodo di omotopia è praticamente insensibile all’aumento del numero di righe.
Tale metodo invece è molto più sensibile all’aumento del numero di componenti non nulle della soluzione: il motivo è da ricercarsi nel fatto che questo metodo risolve, ad ogni passo, un sistema lineare le cui dimensioni sono proporzionali al numero di componenti non nulle dell’attuale iterata x(j), perciò, all’aumentare di kx∗k0, questo metodo necessita di un numero di passi maggiore, il cui costo cresce via via che si aggiungono componenti non nulle. Gli altri due metodi invece esibiscono una sensibilità inferiore rispetto all’aumento delle componenti non nulle.
Capitolo 4. Sperimentazione numerica 400 450 500 550 600 650 700 750 800 850 900 numero di righe m 10-2 10-1 100 101 tempo di esecuzione (s) Omotopia pdNCG IPM 400 450 500 550 600 650 700 750 800 850 900 numero di righe m 0 0.5 1 1.5 2 2.5 tempo di esecuzione (s) Omotopia pdNCG IPM
4.3. Confronto dei metodi 50 100 150 200 250 nnz(x*) 10-2 10-1 100 101 tempo di esecuzione (s) Omotopia pdNCG IPM 50 100 150 200 250 nnz(x*) 0 0.5 1 1.5 2 2.5 tempo di esecuzione (s) Omotopia pdNCG IPM
Bibliografia
[1] A. K. Aziz, I. Babuška, The Mathematical Foundations of the Finite Element Method with Applications to Partial Differential Equations, Academic Press, 1972.
[2] E. van den Berg, M. P. Friedlander, G. Hennenfent, F. J. Herrmann, R. Saab, Ö. Yılmaz, Sparco: A testing framework for sparse reconstruction, Tech. Rep. TR-2007-20, Dept. Computer Science, University of British Columbia, Vancouver, 2007.
[3] D. P. Bertsekas, Nonlinear Programming, Athena Scientific, 1999.
[4] H. Brezis, Functional analysis, Sobolev spaces and partial differential equations, Springer Science & Business Media, 2010.
[5] S. Brugiapaglia, F. Nobile, S. Micheletti, S. Perotto, A theoretical study of COmpRessed SolvING for advection-diffusion-reaction problems, No. EPFL- ARTICLE-211261, 2015.
[6] S. Brugiapaglia, S. Micheletti, S. Perotto. Compressed solving: A numerical ap- proximation technique for elliptic PDEs based on Compressed Sensing, Computers & Mathematics with Applications 70 (2015): 1306-1335.
[7] E. J. Candès, Compressive sampling, Proceedings of the international congress of mathematicians 3, Madrid, 2006.
[8] E. J. Candès, M. Rudelson, T. Tao, R. Vershynin, Error correction via linear programming, 46th Annual IEEE Symposium on Foundations of Computer Science, 2005.
[9] R. H. Chan, T. F. Chan, H. M. Zhou. Advanced signal processing algorithms, Pro- ceedings of the International Society of Photo-Optical Instrumentation Engineers, 1995: 314-325.
[10] T. F. Chan, G. H. Golub, P. Mulet, A nonlinear primal-dual method for total variation-based image restoration, SIAM journal on scientific computing 20 (1999): 1964-1977.
Bibliografia
[11] F. Curtis, J. Nocedal, Steplength selection in interior-point methods for quadratic programming, Applied mathematics letters 20 (2007): 516-523.
[12] J. Dai, W. Xu, J. Zhang, C. Chang, Homotopy algorithm for `1-norm minimisation problems, IET Signal Processing 9 (2015): 1-9.
[13] I. Dassios, K. Fountoulakis, J. Gondzio, A Preconditioner for a Primal-Dual Newton Conjugate Gradients Method for Compressed Sensing Problems, SIAM Journal on Scientific Computing 37 (2015): A2783-A2812.
[14] I. Dassios, K. Fountoulakis, J. Gondzio, A second-order method for compressed sensing problems with coherent and redundant dictionaries, Technical Report ERGO-14-007, 2014.
[15] B. Efron, T. Hastie et al., Least angle regression, The Annals of Statistics 32 (2004): 407-499.
[16] M. H. Firooz, S. Roy. Network tomography via compressed sensing, Global Telecommunications Conference (GLOBECOM 2010), 2010 IEEE.
[17] M. Fornasier, H. Rauhut, Compressive Sensing, In “Handbook of mathematical methods in imaging”, ed. by O. Scherzer (Springer, New York, 2011), pp. 187–228. [18] S. Foucart, H. Rauhut, A mathematical introduction to compressive sensing,
Birkhäuser, 2013.
[19] K. Fountoulakis, J. Gondzio, A second-order method for strongly convex `1- regularization problems, , Mathematical Programming 156 (2016): 189-219. [20] K. Fountoulakis, J. Gondzio, Performance of first-and second-order methods for
big data optimization, Technical Report ERGO-15-005, 2015.
[21] K. Fountoulakis, J. Gondzio, P. Zhlobich, Matrix-free interior point method for compressed sensing problems, Mathematical Programming Computation 6 (2014): 1-31.
[22] J. Gondzio, Interior point methods 25 years later, European Journal of Operational Research 218 (2012): 587-601.
[23] J. B. Hiriart-Urruty, C. Lemaréchal, Convex Analysis and Minimization Algorithms I, Springer, 1993.
[24] J. Mairal, R. Jenatton, G. Obozinski, F. Bach, Convex and network flow opti- mization for structured sparsity, The Journal of Machine Learning Research 12 (2011): 2681-2720.
[25] R. Marks, Introduction to Shannon sampling and interpolation theory, Springer Science & Business Media, 1991.
Bibliografia
[26] P. Richtárik, M. Takáč, Parallel Coordinate Descent Methods for Big Data Optimization, Mathematical Programming 156 (2016): 433-484.
[27] R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970.
[28] S. Rosset, J. Zhu, Piecewise linear regularized solution paths, The Annals of Statistics 35 (2007): 1012-1030.
[29] T. Strohmer, R. W. j. Heath, Grassmanian frames with applications to coding and communication, Applied and computational harmonic analysis 14 (2003): 257-275.
[30] Y. Vardi, Network tomography: estimating source-destination traffic intesities from link data, Journal of the American Statistical Association 91 (1996): 365- 377.
[31] A. Y. Yang, S. S. Sastry, A. Ganesh, Y. Ma, A review of fast `1-minimization
algorithms for robust face recognition, 17th IEEE International Conference on Image Processing (2010): 1849-1852.
[32] G. Yuan, C. Ho, C. J. Lin, Recent Advances of Large-Scale Linear Classification, Proceedings of the IEEE 100 (2012): 2584-2603.