@PhDThesis{ itlic:2014-003,
author = {Liang Dai},
title = {On Several Sparsity Related Problems and the Randomized
{K}aczmarz Algorithm},
school = {Department of Information Technology, Uppsala University},
department = {Division of Systems and Control},
year = {2014},
number = {2014-003},
type = {Licentiate thesis},
month = apr,
day = {9},
abstract = {This thesis studies several problems related to recovery
and estimation. Specifically, these problems are about
sparsity and low-rankness, and the randomized Kaczmarz
algorithm. This thesis includes four papers referred to as
Paper A, Paper B, Paper C, and Paper D.
Paper A considers how to make use of the fact that the
solution to an overdetermined system is sparse. This paper
presents a three-stage approach to accomplish the task. We
show that this strategy, under the assumptions as made in
the paper, achieves the oracle property.
In Paper B, a Hankel-matrix completion problem arising in
system theory is studied. The use of the nuclear norm
heuristic for this basic problem is considered. Theoretical
justification for the case of a single real pole is given.
Results show that for the case of a single real pole, the
nuclear norm heuristic succeeds in the matrix completion
task. Numerical simulations indicate that this result does
not always carry over to the case of two real poles.
Paper C discusses a screening approach for improving the
computational performance of the Basis Pursuit De-Noising
problem. The key ingredient for this work is to make use of
an efficient ellipsoid update algorithm. The results of the
experiments show that the proposed scheme can improve the
overall time complexity for solving the problem.
Paper D studies the choice of the probability distribution
for implementing the row-projections in the randomized
Kaczmarz algorithm. This relates to an open question in the
recent literature. The result proves that a probability
distribution resulting in a faster convergence of the
algorithm can be found by solving a related Semi-Definite
Programming optimization problem.}
}