Convex optimization for signal processing problems

Abstract

Convex optimization has been one of the most exciting research areas in optimization, and it refers to minimizing a convex objective function subject to convex constraints. By recognizing or formulating the optimization problem in convex form, the problem can be solved it efficiently. In the recent decade, convex optimization has become an essential tool in engineering because of the benefits from two convex properties. First, convex optimization gives a globally optimal solution which can be found effi- ciently and reliably. Second, the optimization problem can be computed within any desired accuracy using well-developed numerical methods. Once the convex problem is formed, the problem is claimed to be solved. Source localization, sinusoidal parameter estimation, polynomial root finding and the determination of the capacity region, which are important areas of signal pro- cessing, will be tackled with convex optimization perspective. The problems are first formulated as optimization problems and they are either relaxed or transformed as convex problems to yield global solutions and high-fidelity approximation. In source localization problems, the positions of targets, such as sensor or mobile terminal are the parameters of interest. Given position-bearing measurements, such as time-of-arrival or time-different-of-arrival with the known coordinates of receivers, the target positions are able to be obtained. These problems, especially for time-of- arrival based localization, have been extended to multiple sources in a collaborative environment, which is called sensor network node localization. However, most liter- ature concentrates on the case that the anchor positions and the propagation speed are perfectly known. In this thesis, node localization in the presence of uncertainties in anchor positions and/or propagation speed are dealt with. Furthermore, source localization in non-line-of-sight propagation, which contributes to significant error, is addressed. Source localization using time-different-of-arrival measurements is also studied based on convex optimization. Parameter estimators of several sinusoidal models, namely, single complex/real tone, multiple complex sinusoids, single two-dimensional complex tone and polyno- mial phase signal, in the presence of additive Gaussian noise are developed with convex perspective. The major difficulty for optimally determining the parameters is that the corresponding maximum-likelihood estimators involve searching the global minimum or maximum of multi-modal cost functions because of the nonlinearity of frequencies in the observed signals. By relaxing the non-convex maximum-likelihood formulations using semidefinite programs, high-fidelity approximate solutions are ob- tained in a globally optimum fashion. The problem of solving a polynomial equation has been a classical problem in mathematics. Semidefinite relaxation, which is a branch of convex optimization tech- nique, is investigated to find real roots of a real polynomial. The determination of the capacity region of parallel Gaussian interference channels is an open problem. The special case where the channel is one-sided is considered. The sum capacity cost function of user powers is shown to be convex. Exploiting the inherent structure of the problem, a numerical algorithm is constructed to compute the sum capacity.

Date of Award	2 Oct 2009
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Hing Cheung SO (Supervisor)