M.Sc Thesis

M.Sc StudentEshel Ronen
SubjectAspects of Convex Optimization and Concentration in Coding
DepartmentDepartment of Electrical and Computer Engineering
Supervisor PROF. Igal Sason
Full Thesis textFull thesis text - English Version


The thesis consists of three main parts. The first part of the work considers the complexity of the interior-point method (IPM) for solving convex optimization problems. We prove upper bounds on the number of Newton iterations needed to solve a convex optimization problem whose objective function is self concordant (s.c.). Several bounds are given for various step size algorithms: Newton’s method with backtracking line-search and two choices of pre-determined step size. Compared to previous bounds, the new bounds are 10-100 times tighter. Using computer simulations, we explore the properties of those new tightened bounds.

The second part of the thesis considers the problem of decoding linear block codes (e.g., low-density parity-check codes (LDPC)) using Linear Programming (LP). We apply the bounds derived earlier on an IPM-based LP decoder in order to obtain a complexity bound on the number of iterations of the LP decoder. Next, we optimize the bound in order to obtain an optimized set of IPM parameters based on the code and channel parameters (i.e., block length, parity-check matrix row degree, noise level, etc..). The bound derived gives an analytic insight on the decoding complexity as a function of the code and channel parameters.

The third part of the work (which stands by itself) considers the concentration of measures for LDPC code ensembles. The results derived in this thesis follow from Azuma-Hoeffding inequality for Doob’s martingales with bounded differences. The first result is a tightened concentration inequality for the conditional entropy (originally derived by M?easson et al.). Next, several concentration results on the number of erroneous variable-to-check node messages for inter-symbol-interference (ISI) channels are proved. The analysis provides an explicit expression for the exponential decay of the concentration inequalities given by Kavci?c et al. It is shown that specializing these results for memoryless channels provides tightened concentration inequalities as compared to previous results by Luby et al. and Richardson & Urbanke.