Title: Solving underdetermined systems with error-correcting codes

Authors: Ted Hurley

Addresses: Department of Mathematics, National University of Ireland Galway, Galway, Ireland

Abstract: In an underdetermined system of equations Aw = y, where A is an m × n matrix, only u of the entries of y with u < m are known. Thus E_jw, called 'measurements', are known for certain j ∈ J ⊂ {0, 1, . . . , m – 1} where {E_i, i = 0, 1, . . . , m – 1} are the rows of A and |J| = u. It is required, if possible, to solve the system uniquely when x has at most t non-zero entries with u ≥ 2t. Here such systems are considered from an error-correcting coding point of view. This reduces the problem to finding a suitable decoding algorithm which then finds w. Decoding workable algorithms are shown to exist, from which the unknown w may be determined, in cases where the known 2t values are evenly spaced, that is when the elements of J are in arithmetic sequence. The method can be applied to Fourier matrices and certain classes of Vandermonde matrices. The decoding algorithm has complexity O(nt) and in some cases the complexity is O(t²). Matrices which have the property that the determinant of any square submatrix is non-zero are of particular interest. Randomly choosing rows of such matrices can then give t error-correcting pairs to generate a 'measuring' code. This has applications to signal processing and compressed sensing.

Keywords: codes; compressed sensing; signal processing; underdetermined system.

DOI: 10.1504/IJICOT.2017.086886

International Journal of Information and Coding Theory, 2017 Vol.4 No.4, pp.201 - 221

Received: 05 Aug 2016
Accepted: 10 Oct 2016
Published online: 02 Oct 2017 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article