lq sparse signal estimation with applications

The use of sparsity has emerged in the last fifteen years as an important tool for solving many problems in the areas of signal processing and statisticalinference. In this dissertation we pursue three significant applications of sparsity; sparse linear regression, low rank matrix completion and sparseinverse covariance selection. In the first and third topic, sparsity refers to having a small number of nonzero vector and matrix entries respectively,while in the second topic it is associated with low matrix rank.A penalized approach is considered involving optimization of an objective function with two terms. One of the terms measures the goodness of fit i.e.the error between the observed data and the estimated solution, while the other is a penalty responsible for inducing sparse solutions, hence the namepenalized problem.It is well understood that the natural way of inducing sparsity is through the l0 ``norm'' i.e. the counting function or the discrete metric. Since the l0function is non convex, a large volume of literature has instead resorted to using the convex l1 norm as the penalty. Therefore, the failure to consider thel0 penalized problem is a point of departure for this dissertation. In order to bridge the gap between the l0 and l1 penalties, the focus becomes thedevelopment of non convex optimization methods for the lq (00 but the emphasis is on 0<q<1. Imposing basic assumptions, we prove that theiterates converge to a stationary point, and if this point is a local minimizer then it is also proved that the convergence is R-linear. Simulations are giventhat illustrate the potential of considering the use of our algorithm.Chapter 4 considers the topic of low rank matrix completion, where we develop an algorithm for optimizing an lq (rank) penalized least squares problemwith 0<q<1. In the development process we solve a non-trivial one dimensional lq optimization problem that is fundamental to our work. Additionally, ageneral algorithm convergence (fixed point) result with a non-trivial proof is given for 0&#8804;q<1. We illustrate with data analysis examples, comparing thereconstruction quality of three matrix singular value penalties: l0, l1 and lq, 0<q<1.Chapter 5 considers the topic of sparse inverse covariance estimation, where we develop an algorithm for optimizing an lq penalized log-likelihoodproblem with 0&#8804;q<1. The development requires the solutions of the one dimensional lq optimization problem from Chapter 4. These are additionallyused to prove some algorithm properties as well as some fixed point results. We illustrate with simulations and a real world application example.Reconstruction comparisons are given using four penalties: l0, l1, lq with 0<q