Tractable relaxations and efficient algorithmic techniques for large-scale optimization

In this thesis, we develop tractable relaxations and efficient algorithms for large-scale optimization. Our developments are motivated by a recent paradigm, Compressed Sensing, which covers a multitude of large-scale, sparsity-oriented convex optimization problems. Compressed sensing is focused on the recovery of sparse or well-concentrated signals from possibly noisy observations in a low-dimensional space. Nowadays, this theory is successfully utilized in many fields ranging from MRI image processing to machine learning, from biology to statistics. In the first chapter of this thesis, we provide a general introduction to compressed sensing and its applications and cover some of the earlier results. The majority of results in compressed sensing theory rely on the ability to design/use projection matrices with good recoverability properties. In the second chapter of this thesis, we study the conditions for good recoverability properties of a sensing matrix. We propose necessary and sufficient conditions for a sensing matrix to allow for exact e1-recovery of sparse signals with at most s nonzero entries while utilizing a priori information given in the form of sign restrictions on part of the entries. We express error bounds for imperfect e1-recovery in terms of the characteristics underlying these conditions. These characteristics, although difficult to evaluate, lead to two different verifiable sufficient conditions, which can be efficiently computed via linear programming (LP) and/or semidefinite programming (SDP) and thus generate efficiently computable lower bounds on the level of sparsity, s, for which a given sensing matrix is shown to allow for exact e1-recovery. We analyze the connection between our LP- and SDP-based verifiable sufficient conditions, examine their properties, describe their limits of performance and provide numerical examples comparing them with other verifiable conditions from the literature. Even though our LP- and SDP-based relaxations are presented in CS framework, these techniques are generic and applicable in the case of disjoint bilinear programs. In the third chapter, we study the compressed sensing synthesis problem – selecting the minimum number of rows from a given matrix, so that the resulting submatrix possesses certifiably good recovery properties. Starting from the verifiable sufficient conditions, we express the synthesis problem as the problem of approximating a given matrix by a matrix of specified low rank in the uniform norm. We develop a randomized algorithm for efficient construction of rank k approximation of matrices of size m × n achieving accuracy bounds O(1) lnmn /k which hold in expectation or with high probability. We supply a derandomized version of our approximation algorithm and provide numerical results on its performance for the synthesis problem. Chapter 4 is dedicated to efficient first-order algorithms for large-scale, well-structured convex optimization problems. Saddle point reformulation is proven to be an effective tool to exploit problem structure for designing computationally efficient algorithms. Building upon their strength, we first demonstrate that the solutions to many large-scale problems arising from compressed sensing recovery, high-dimensional statistical inference, and machine learning can be obtained through solving a series of Bilinear Saddle Point problems (BSPs). We accelerate the solution of associated single-parametric BSP's by utilizing the Mirror Prox algorithm from [101] as a prototype and by replacing precise first order oracle (which becomes quite time-consuming in the extremely large-scale case) by its computationally cheap randomized counterpart. In the overall solution of parametric BSPs, cheap online assessment of solution quality is crucial. Our randomized algorithms come with exact guarantees on solution quality and achieves sublinear time behavior to solve large-scale parametric BSPs. Extensive simulations show that our randomized first-order methods are capable of handling very large-scale applications and improve considerably over the state-of-the-art deterministic algorithms, with benefits amplifying as the sizes of the problems grow. In the fifth chapter, we examine a more general sparse estimation problem – estimating a signal from its undersampled observations corrupted with nuisance and stochastic noise. Instead of the standard sparse signal framework, here we work under the assumption that a priori information is presented via a block representation structure of a known linear transform of the signal, and the signal achieves a good approximation in block sparse sense in this representation structure. There are a number of important applications where such a nontrivial sparsifying representation arises naturally such as standard image reconstruction with Total Variation regularization or finding the solution of a linear finite-difference equation with sparse right hand side (“evolution of a linear plant corrected from time to time by impulse control”). We show that an extension of the standard compressed sensing results from [79] to this framework is possible. Particularly, we introduce a family of conditions, suggest two new methods of recovery based on block-e 1 minimization and study the most common cases of the block representation structure under which these estimators have efficiently verifiable guaranties of performance. We link our performance estimations to the well known results of compressed sensing by providing connections between our conditions and Restricted Isometry Property. This also establishes connections between new techniques and classical methods such as Lasso and Dantzig Selector. We present a summary of conclusions of our study and provide future research directions in the last chapter.