The unifying theme of this dissertation is the development of new solutions for decoding and inference problems based on convex optimization methods. Th first part considers the joint detection and decoding problem for low-density parity-check (LDPC) codes on finite-state channels (FSCs). Hard-disk drives (or magnetic recording systems), where the required error rate (after decoding) is too low to be verifiable by simulation, are most important applications of this research. Recently, LDPC codes have attracted a lot of attention in the magnetic storage industry and some hard-disk drives have started using iterative decoding. Despite progress in the area of reduced-complexity detection and decoding algorithms, there has been some resistance to the deployment of turbo-equalization (TE) structures (with iterative detectors/decoders) in magnetic-recording systems because of error floors and the difficulty of accurately predicting performance at very low error rates. To address this problem for channels with memory, such as FSCs, we propose a new decoding algorithms based on a well-defined convex optimization problem. In particular, it is based on the linear-programing (LP) formulation of the joint decoding problem for LDPC codes over FSCs. It exhibits two favorable properties: provable convergence and predictable error-floors (via pseudo-codeword analysis). Since general-purpose LP solvers are too complex to make the joint LP decoder feasible for practical purposes, we develop an efficient iterative solver for the joint LP decoder by taking advantage of its dual-domain structure. The main advantage of this approach is that it combines the predictability and superior performance of joint LP decoding with the computational complexity of TE. The second part of this dissertation considers the matrix completion problem for the recovery of a data matrix from incomplete, or even corrupted entries of an unknown matrix. Recommender systems are good representatives of this problem, and this research is important for the design of information retrieval systems which require very high scalability. We show that our IMP algorithm reduces the well-known cold-start problem associated with collaborative filtering systems in practice.

A non-iterative receiver is proposed to achieve near capacity performance on intersymbol interference (ISI) channels. There are two main ingredients in the proposed design. i) The use of a novel BCJR-DFE equalizer which produces optimal soft estimates of the inputs to the ISI channel given all the observations from the channel and L past symbols exactly, where L is the memory of the ISI channel. ii) The use of an encoder structure that ensures that L past symbols can be used in the DFE in an error free manner through the use of a capacity achieving code for a memoryless channel. Computational complexity of the proposed receiver structure is less than that of one iteration of the turbo receiver. We also provide the proof showing that the proposed receiver achieves the i.i.d. capacity of any constrained input ISI channel. This DFE-based receiver has several advantages over an iterative (turbo) receiver, such as low complexity, the fact that codes that are optimized for memoryless channels can be used with channels with memory, and finally that the channel does not need to be known at the transmitter. The proposed coding scheme is universal in the sense that a single code of rate r; optimized for a memoryless channel, provides small error probability uniformly across all AWGN-ISI channels of i.i.d. capacity less than r: This general principle of a proposed non-iterative receiver also applies to other signal processing functions, such as timing recovery, pattern-dependent noise whiten ing, joint demodulation and decoding etc. This makes the proposed encoder and receiver structure a viable alternative to iterative signal processing. The results show significant complexity reduction and performance gain for the case of timing recovery and patter-dependent noise whitening for magnetic recording channels.