THESIS
2018

xv, 124 pages : color illustrations ; 30 cm

**Abstract**
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.

## Post a Comment

Your email address will not be published. Required fields are marked *