On semidefinite programming and vector quantization with application to image coding

This thesis focuses on the development of algorithms for solving semidefinite programs and designing vector quantization (VQ) systems with application to image coding.; Semidefinite programs directly arise in many electrical engineering applications. A semidefinite program is a nonlinear and nondifferentiable, but convex optimization problem. It covers several standard optimization problems such as linear and quadratic programming. Interior-point methods have been shown to be very efficient for solving semidefinite programs. In this thesis, a less expensive, quadratically but locally convergent algorithm is presented. It can be combined with interior-point methods to solve semidefinite programs more efficiently. Since this local method requires estimating a certain eigenvalue multiplicity at the solution. A non-heuristic eigenvalue multiplicity estimation algorithm is also developed. Then two exterior minimum penalty path following methods are developed. These methods do not require the existence of interior-points and achieve a solution from the exterior of the constraint set.; The design algorithms for vector quantization with application to image coding are developed from the optimization point of view in this thesis. First, an existing fast search algorithm for VQ encoding is improved by showing that the projections of quantization regions can be obtained by solving certain linear programs. Then a new design algorithm for entropy constrained residual VQ is proposed. The algorithm converges and has better performance than existing algorithms at low bit rates. Finally, a lossless coding method for VQ indices is developed by context modeling of neighboring image VQ indices. It produces very promising results.