Tianyi Liu

In this paper, we consider the maximum a posteriori (MAP) estimation for the multiple measurement vectors (MMV) problem with application to direction-of-arrival (DOA) estimation, which is classically formulated as a regularized least-squares (LS) problem with an \ell_2,0-norm constraint, and derive an equivalent mixed-integer semidefinite program (MISDP) reformulation. The proposed MISDP reformulation can be exactly solved by a generic MISDP solver using a semidefinite programming (SDP) based branch-and-bound method, which, unlike other nonconvex approaches for the MMV problem, such as the greedy methods and sparse Bayesian learning techniques, provides a solution with an optimality assessment even with early termination. We also present an approximate solution approach based on randomized rounding that yields high-quality feasible solutions of the proposed MISDP reformulation at a practically affordable computation time for problems of extremely large dimensions. Numerical simulations demonstrate the improved error performance of our proposed method in comparison to several popular DOA estimation methods. In particular, compared to the deterministic maximum likelihood (DML) estimator, which is often used as a benchmark, the proposed method applied with the randomized rounding algorithm exhibits a superior estimation performance at a significantly reduced running time.

Spatial frequency estimation from a mixture of noisy sinusoids finds applications in various fields. While subspace-based methods offer cost-effective super-resolution parameter estimation, they demand precise array calibration, posing challenges for large antennas. In contrast, sparsity-based approaches outperform subspace methods, especially in scenarios with limited snapshots or correlated sources. This study focuses on direction-of-arrival (DOA) estimation using a partly calibrated rectangular array with fully calibrated subarrays. A gridless sparse formulation leveraging shift invariances in the array is developed, yielding two competitive algorithms under the alternating direction method of multipliers (ADMM) and successive convex approximation frameworks, respectively. Numerical simulations show the superior error performance of our proposed method, particularly in highly correlated scenarios, compared to the conventional subspace-based methods. It is demonstrated that the proposed formulation can also be adopted in the fully calibrated case to improve the robustness of the subspace-based methods to the source correlation. Furthermore, we provide a generalization of the proposed method to a more challenging case where a part of the sensors is unobservable due to failures.

This dissertation is concerned with the design and analysis of approximation-based methods for nonconvex nonsmooth optimization problems. The main idea behind those methods is to solve a difficult optimization problem by converting it into a sequence of simpler surrogate/approximate problems. In the two widely-used optimization frameworks, namely, the majorization-minimization (MM) framework and the successive convex approximation (SCA) framework, the approximate function is designed to be a global upper bound, called majorizer, of the original objective function and convex, respectively. Generally speaking, there are two desiderata of the approximate function, i.e., the tightness to the original objective function and the low computational complexity of minimizing the approximate function. In particular, we focus on techniques that can be used to construct a parallelizable approximate problem so as to take advantage of modern multicore computing platforms. The first part of this thesis aims to develop an efficient parallelizable algorithmic framework based on approximation techniques for a broad class of nonconvex nonsmooth optimization problems. The classic convergence result of MM is established on the consistency of directional derivatives in all directions between the original objective function and its majorizer at the point where the majorizer is constructed. This requirement restricts the majorizer constructed at a nondifferentiable point of the original function to be also nonsmooth, which hinders its capability of simplifying nonsmooth problems since the minimization of the majorizing function, if restricted to be nonsmooth, may still be difficult. Therefore, in this thesis, we relax the derivative consistency in the majorization step so that a smooth majorizer that can be easily minimized is permitted for a wide class of nonsmooth problems. As a result of this relaxation of derivative consistency, the smoothing majorization leads to the convergence to a stationary solution in a more relaxed sense than the classic MM. Furthermore, in contrast to minimizing the possibly nonconvex majorizing function exactly, the smoothness of the majorizing function allows us to employ the idea of SCA, along with available separable approximation techniques, to obtain an approximate minimizer of the majorizing function efficiently. Thus, we develop a parallelizable inexact MM framework, termed smoothing SCA, by combining the smoothing majorization technique and the idea of successive convex approximation. In this framework, the construction of the approximate problem at each iteration is divided into two steps, namely, the smoothing majorization and the convex approximation, so that the two desiderata of the approximate function can be treated separately. In addition, both the exact and inexact MM with smoothing majorization can be implemented block-coordinatewise to exploit potential separable structures of the constraints in the optimization problem. The convergence behaviors of the proposed frameworks are analyzed accordingly. In the second part of this thesis, as our mainly promoted framework, the smoothing SCA framework is employed to address the phase retrieval with dictionary learning problem. Two efficient parallel algorithms are developed by applying the smoothing SCA to two complementary nonconvex nonsmooth formulations, respectively, which are both based on a least-squares criterion. The computational complexities of the proposed algorithms are theoretically analyzed and both their error performance and computational time are evaluated by extensive simulations in the context of blind channel estimation from subband magnitude measurements in multi-antenna random access network, in comparison to the state-of-the-art methods.

Phase retrieval aims at recovering unknown signals from magnitude measurements of linear mixtures. In this paper, we consider the phase retrieval with dictionary learning problem, which includes another prior information that the signal admits a sparse representation over an unknown dictionary. The task is to jointly estimate the dictionary and the sparse representation from magnitude-only measurements. To this end, we study two complementary formulations and develop efficient parallel algorithms by extending the successive convex approximation framework using a smooth majorization. The first algorithm is termed compact-SCAphase and is preferable in the case of moderately diverse mixture models with a low number of mixing components. It adopts a compact formulation that avoids auxiliary variables. The proposed algorithm is highly scalable and has reduced parameter tuning cost. The second algorithm, referred to as SCAphase, uses auxiliary variables and is favorable in the case of highly diverse mixture models. It also renders simple incorporation of additional side constraints. The performance of both methods is evaluated when applied to blind channel estimation from subband magnitude measurements in a multi-antenna random access network. Simulation results show the efficiency of the proposed techniques compared to state-of-the-art methods.