Sparsity has been successfully applied in almost all the fields of science and engineering, especially in high-dimensional applications, where a sparse representation can reduce the complexity of the problem and increase the interpretability of the result. Among others, it has been used for variable selection, signal recovery, source separation, face recognition, image classification, pattern recognition, signal representation, etc. Although each of these applications has a unique structure and formulation, the ultimate goal is always the same, i.e., acquire, represent or compress a high dimensional signal. Regardless of the application, requiring a sparse solution translates into a non-convex formulation that, in fact, belongs to the NP-hard class. Therefore, there has been a l...[ Read more ]

Sparsity has been successfully applied in almost all the fields of science and engineering, especially in high-dimensional applications, where a sparse representation can reduce the complexity of the problem and increase the interpretability of the result. Among others, it has been used for variable selection, signal recovery, source separation, face recognition, image classification, pattern recognition, signal representation, etc. Although each of these applications has a unique structure and formulation, the ultimate goal is always the same, i.e., acquire, represent or compress a high dimensional signal. Regardless of the application, requiring a sparse solution translates into a non-convex formulation that, in fact, belongs to the NP-hard class. Therefore, there has been a lot of research on finding approximate formulations that lead into sparse solutions and on deriving efficient algorithms for solving the variants of sparse approximations. In this dissertation we focus on sparsity methods for high-dimensional applications in the fields of machine learning and finance.

We first consider the problem of estimating sparse eigenvectors of a symmetric matrix that attracts a lot of attention in many applications, especially those with a high dimensional data set. This is the well known principal component analysis (PCA) procedure with a sparsity requirement. PCA is motivated in many machine learning applications, where it is used for dimensionality reduction, correlation and redundancy analysis of the data, etc. While classical eigenvectors can be obtained as the solution of a maximization problem, existing approaches formulate the sparse PCA problem by adding a penalty term into the objective function that encourages a sparse solution. However, the vast majority of the resulting methods achieve sparsity at the expense of sacrificing the orthogonality property. We develop a new method to estimate dominant sparse eigenvectors without trading off their orthogonality. The problem is highly non-convex and hard to handle. We apply the minorization-maximization framework where we iteratively maximize a tight lower bound (surrogate function) of the objective function over the Stiefel manifold. The inner maximization problem turns out to be a rectangular Procrustes problem, which has a closed form solution. In addition, we propose a method to improve the covariance estimation problem when its underlying eigenvectors are known to be sparse. We use the eigenvalue decomposition of the covariance matrix to formulate an optimization problem where we impose sparsity on the corresponding eigenvectors. Numerical experiments show that the proposed eigenvector extraction algorithm outperforms existing algorithms in terms of support recovery and explained variance, while the covariance estimation algorithms improve significantly the sample covariance estimator.

In the second work, we consider the index tracking problem, an application of sparsity coming from the financial industry. Index tracking is a popular passive portfolio management strategy that aims at constructing a portfolio that replicates the performance of an index, e.g., the Hang Seng index in Hong Kong or the S&P 500 in the USA. The tracking error can be minimized by purchasing all the assets of the index in appropriate amounts. However, to avoid small and illiquid positions and large transaction costs it is desired that the tracking portfolio should consist of a small number of assets, i.e., to be sparse. The optimal asset selection and capital allocation can be formulated as a combinatorial problem. A commonly used approach is to use mixed-integer programming (MIP) to solve small sized problems. Nevertheless, MIP solvers can fail for high-dimensional problems while the running time can be prohibiting for practical use. We propose efficient and fast index tracking algorithms assuming a set of general convex constraints. Further, we derive specialized closed-form update algorithms for particular sets of constraints. Numerical simulations show that the proposed algorithms match or outperform existing algorithm in terms of performance, while their running time is lower by many orders of magnitude.