Decoding as a linear ill-posed problem: The entropy minimization approach

The problem of decoding can be thought of as consisting of solving an ill-posed, linear inverse problem with noisy data and box constraints upon the unknowns. Specificially, we aimed to solve $ {{\boldsymbol A}}{{\boldsymbol x}}+{{\boldsymbol e}} = {{\boldsymbol y}}, $ where $ {{\boldsymbol A}} $ is a matrix with positive entries and $ {{\boldsymbol y}} $ is a vector with positive entries. It is required that $ {{\boldsymbol x}}\in{{\mathcal K}} $, which is specified below, and we considered two points of view about the noise term, both of which were implied as unknowns to be determined. On the one hand, the error can be thought of as a confounding error, intentionally added to the coded message. On the other hand, we may think of the error as a true additive transmission-measurement error. We solved the problem by minimizing an entropy of the Fermi-Dirac type defined on the set of all constraints of the problem. Our approach provided a consistent way to recover the message and the noise from the measurements. In an example with a generator code matrix of the Reed-Solomon type, we examined the two points of view about the noise. As our approach enabled us to recursively decrease the $ \ell_1 $ norm of the noise as part of the solution procedure, we saw that, if the required norm of the noise was too small, the message was not well recovered. Our work falls within the general class of near-optimal signal recovery line of work. We also studied the case with Gaussian random matrices.