Efficient optimization methods play a central role in numerous applications in machine learning and signal processing where optimization problems are involved. With the explosion of data in recent years, they have been even more important as problems of interest are becoming more and more high-dimensional. The main focus of this dissertation is on the development of efficient optimization algorithms based on the majorization-minimization (MM) framework for some high-dimensional optimization problems of particular interest.

We first consider an l₀-norm penalized formulation of the generalized eigenvalue problem (GEP), which is extremely useful in numerous applications of high dimensional data analysis and machine learning, for instance gene expression data analysis. By adding the l₀-no...[ Read more ]

Efficient optimization methods play a central role in numerous applications in machine learning and signal processing where optimization problems are involved. With the explosion of data in recent years, they have been even more important as problems of interest are becoming more and more high-dimensional. The main focus of this dissertation is on the development of efficient optimization algorithms based on the majorization-minimization (MM) framework for some high-dimensional optimization problems of particular interest.

We first consider an l₀-norm penalized formulation of the generalized eigenvalue problem (GEP), which is extremely useful in numerous applications of high dimensional data analysis and machine learning, for instance gene expression data analysis. By adding the l₀-norm penalization term, we aim at extracting the leading sparse generalized eigenvector of a matrix pair. To tackle the problem, we first approximate the l₀-norm by a continuous surrogate function. Then an algorithm is developed via iteratively majorizing the surrogate function by a quadratic separable function, which at each iteration reduces to a regular generalized eigenvalue problem. For sparse GEPs with special structure, algorithms that admit a closed-form solution at every iteration are also derived.

The second problem that we have considered is the design of unit-modulus sequences with good autocorrelation properties, which has extensive applications in active sensing and communication systems, for example radar systems and code-division multiple access (CDMA) cellular systems. Different metrics, including the integrated sidelobe level (ISL), the weighted integrated sidelobe level (WISL) and the peak sidelobe level (PSL), have been considered to measure the goodness of the autocorrelation property. New algorithms are developed based on the MM framework to minimize the different metrics over the set of unit-modulus sequences. All the proposed algorithms can be implemented via fast Fourier transform (FFT) operations and thus are computationally efficient. Furthermore, after some modifications the algorithms can be adapted to incorporate spectral constraints, which makes the design more flexible. Numerical experiments show that the proposed algorithms outperform existing algorithms in terms of both the quality of designed sequences and the computational complexity.