Computational approaches for the sparse regression problem

dc.contributorVelasco Gregory, Mauricio Fernando
dc.contributorBogart, Tristram Charles
dc.contributorMuñoz Durango, Diego Alejandro
dc.creatorMora Potes, José Luis
dc.date.accessioned2022-07-19T15:00:31Z
dc.date.available2022-07-19T15:00:31Z
dc.date.created2022-07-19T15:00:31Z
dc.date.issued2022
dc.identifierhttp://hdl.handle.net/1992/58967
dc.identifierinstname:Universidad de los Andes
dc.identifierreponame:Repositorio Institucional Séneca
dc.identifierrepourl:https://repositorio.uniandes.edu.co/
dc.description.abstractThis work introduces and describes three different formulations (and their respective algorithms) for the sparse regression problem and compare their performance under different models. Lastly, it presents an application to tensor algebra which consists of formulating the problem of finding the tensor rank for the 2x2 matrix multiplication and the polynomial multiplication tensor as sparse regression models (using the ideas of Strassen's algorithm and Karatsuba's algorithm, respectively), and then applying the formulations previously introduced to solve them.
dc.description.abstractEste trabajo realiza una recopilación de diferentes formulaciones (con sus respectivos algoritmos) del problema de regresión dispersa y compara el desempeño de estas para modelos de diferentes tamaños. Por último, se presenta una aplicación en el campo del álgebra tensorial que consiste en formular el problema de hallar el rango del tensor de multiplicación de matrices 2x2 y el de multiplicación de polinomios como modelos de regresión dispersa (usando el algoritmo de Strassen y el algoritmo de Karatsuba, respectivamente) y se buscan soluciones a partir de las formulaciones introducidas anteriormente.
dc.languageeng
dc.publisherUniversidad de los Andes
dc.publisherMaestría en Matemáticas
dc.publisherFacultad de Ciencias
dc.publisherDepartamento de Matemáticas
dc.relationP. Bühlmann and S. Van De Geer, Statistics for high-dimensional data: methods, theory and applications. Springer Science & Business Media, 2011.
dc.relationT. Hastie, R. Tibshirani, and M. Wainwright, Statistical learning with sparsity, Monographs on statistics and applied probability, vol. 143, p. 143, 2015.
dc.relationA. Civril, A note on the hardness of sparse approximation, Information Processing Letters, vol. 113, no. 14-16, pp. 543-545, 2013.
dc.relationU. Feige, A threshold of ln n for approximating set cover,Journal of the ACM (JACM), vol. 45, no. 4, pp. 634-652, 1998.
dc.relationC.-H. Zhang, Nearly unbiased variable selection under minimax concave penalty,The Annals of statistics, vol. 38, no. 2, pp. 894-942, 2010.
dc.relationJ. Fan and R. Li, Variable selection via nonconcave penalized likelihood and its oracle properties, Journal of the American statistical Association, vol. 96, no. 456, pp. 1348-1360, 2001.
dc.relationT. Hastie, R. Tibshirani, J. H. Friedman, and J. H. Friedman, The elements of sta tistical learning: data mining, inference, and prediction, vol. 2. Springer, 2009.
dc.relationT. Blumensath and M. E. Davies, Iterative hard thresholding for compressed sensing, Applied and computational harmonic analysis, vol. 27, no. 3, pp. 265-274, 2009.
dc.relationA. Beck and Y. C. Eldar, Sparsity constrained nonlinear optimization: Optimality conditions and algorithms, SIAM Journal on Optimization, vol. 23, no. 3, pp. 14801509, 2013.
dc.relationD. Bertsimas and B. Van Parys, Sparse high-dimensional regression: Exact scalable algorithms and phase transitions, The Annals of Statistics, vol. 48, no. 1, pp. 300-323, 2020.
dc.relationM. A. Duran and I. E. Grossmann, An outer-approximation algorithm for a class of mixed-integer nonlinear programs, Mathematical programming, vol. 36, no. 3, pp. 307-339, 1986.
dc.relationS. A. Gershgorin, Uber die abgrenzung der eigenwerte einer matrix, no. 6, pp. 749-754, 1931.
dc.relationR. A. Horn and C. R. Johnson, Matrix analysis. Cambridge university press, 2012.
dc.relationW. W. Hager, Updating the inverse of a matrix, SIAM review, vol. 31, no. 2, pp. 221-239, 1989.
dc.relationL. N. Trefethen and D. Bau III, Numerical linear algebra, vol. 50. Siam, 1997.
dc.relationP. Bürgisser, M. Clausen, and M. A. Shokrollahi, Algebraic complexity theory, vol. 315. Springer Science & Business Media, 2013.
dc.relationV. STRASSEN, Gaussian elimination is not optimal., Numerische Mathematik, vol. 13, pp. 354-356, 1969.
dc.relationM. Bläser, On the complexity of the multiplication of matrices of small formats,Journal of Complexity, vol. 19, no. 1, pp. 43-60, 2003.
dc.relationJ. D. Laderman, A noncommutative algorithm for multiplying 3× 3 matrices using 23 multiplications, in Am. Math. Soc, vol. 82, pp. 126-128, 1976.
dc.relationA. A. Karatsuba, The complexity of computations, Proceedings of the Steklov Institute of Mathematics-Interperiodica Translation, vol. 211, pp. 169-183, 1995.
dc.relationK. Ito and B. Jin, Inverse problems: Tikhonov theory and algorithms, vol. 22. World Scientific, 2014.
dc.relationA. N. Tikhonov, On the regularization of ill-posed problems, in Doklady Akademii Nauk, vol. 153, pp. 49-52, Russian Academy of Sciences, 1963.
dc.relationA. N. Tikhonov, On the solution of ill-posed problems and the method of regularization, in Doklady Akademii Nauk, vol. 151, pp. 501-504, Russian Academy of Sciences, 1963.
dc.relationA. N. Tikhonov, On the stability of inverse problems, in Dokl. Akad. Nauk SSSR, vol. 39, pp. 195-198, 1943.
dc.relationF. Zhang, The Schur complement and its applications, vol. 4. Springer Science & Business Media, 2006.
dc.relationD. Bertsimas, J. Pauphilet, and B. Van Parys, Sparse regression: Scalable algorithms and empirical performance, Statistical Science, vol. 35, no. 4, pp. 555-578, 2020.
dc.relationD. Donoho and J. Tanner, Observed universality of phase transitions in high dimensional geometry, with implications for modern data analysis and signal pro cessing, Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, vol. 367, no. 1906, pp. 4273-4293, 2009.
dc.relationM. Wang, W. Xu, and A. Tang, ¿On the performance of sparse recovery via p minimization (0 p 1), IEEE Transactions on Information Theory, vol. 57, no. 11, pp. 7255-7278, 2011.
dc.relationL. Zheng, A. Maleki, H. Weng, X. Wang, and T. Long, Does p-minimization outper form 1-minimization, IEEE Transactions on Information Theory, vol. 63, no. 11, pp. 6896-6935, 2017.
dc.relationD. Bertsimas, A. King, and R. Mazumder, Best subset selection via a modern optimization lens, The annals of statistics, vol. 44, no. 2, pp. 813-852, 2016.
dc.relationJ. A. Tropp, Just relax: Convex programming methods for identifying sparse signals in noise, IEEE transactions on information theory, vol. 52, no. 3, pp. 1030-1051, 2006.
dc.relationY. Nesterov, Introductory lectures on convex optimization: A basic course, vol. 87. Springer Science & Business Media, 2003.
dc.relationR. Tibshirani, Regression shrinkage and selection via the lasso, Journal of the Royal Statistical Society: Series B (Methodological), vol. 58, no. 1, pp. 267-288, 1996.
dc.relationM. J. Wainwright, Sharp thresholds for high-dimensional and noisy sparsity recovery using 1-constrained quadratic programming (lasso), IEEE transactions on information theory, vol. 55, no. 5, pp. 2183-2202, 2009.
dc.relationJ. M. Landsberg, Tensors: geometry and applications, Representation theory, vol. 381, no. 402, p. 3, 2012.
dc.relationM. Lubin, E. Yamangil, R. Bent, and J. P. Vielma, Polyhedral approximation in mixed-integer convex optimization,¿ Mathematical Programming, vol. 172, no. 1, pp. 139-168, 2018.
dc.relationS. Boyd, S. P. Boyd, and L. Vandenberghe, Convex optimization. Cambridge university press, 2004.
dc.relationG. Ballard, C. Ikenmeyer, J. M. Landsberg, and N. Ryder, The geometry of rank decompositions of matrix multiplication ii: 3× 3 matrices, Journal of Pure and Applied Algebra, vol. 223, no. 8, pp. 3205-3224, 2019.
dc.relationJ. M. Landsberg and M. Michaek, On the geometry of border rank decompositions for matrix multiplication and other tensors with symmetry, SIAM Journal on Applied Algebra and Geometry, vol. 1, no. 1, pp. 2-19, 2017.
dc.relationA. Miller, Subset selection in regression. chapman and hall/CRC, 2002.
dc.relationH. Hazimeh and R. Mazumder, Fast best subset selection: Coordinate descent and local combinatorial optimization algorithms, Operations Research, vol. 68, no. 5, pp. 1517-1537, 2020.
dc.rightsAttribution-NonCommercial-NoDerivatives 4.0 Internacional
dc.rightshttp://creativecommons.org/licenses/by-nc-sa/4.0/
dc.rightsinfo:eu-repo/semantics/openAccess
dc.rightshttp://purl.org/coar/access_right/c_abf2
dc.titleComputational approaches for the sparse regression problem
dc.typeTrabajo de grado - Maestría


Este ítem pertenece a la siguiente institución