@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.}
}