Solving underdetermined systems with error-correcting codes

DOI10.1504/IJICOT.2017.10005825zbMATH Open1407.94011arXiv1509.03784MaRDI QIDQ725952

Ted Hurley

Publication date: 2 August 2018

Published in: International Journal of Information and Coding Theory (Search for Journal in Brave)

Abstract: In an underdetermined system of equations $Ax=y$, where $A$ is an $mimesn$ matrix, only $u$ of the entries of $y$ with $u<m$ are known. Thus $E_{j}w$, called `measurements', are known for certain $jinJsubset0,1,ldots,m-1$ where $E_i,i=0,1,ldots,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 $ugeq2t$. Here such systems are considered from an error-correcting coding point of view. The unknown $x$ can be shown to be the error vector of a code subject to certain conditions on the rows of the matrix $A$. This reduces the problem to finding a suitable decoding algorithm which then finds $x$. Decoding workable algorithms are shown to exist, from which the unknown $x$ may be determined, in cases where the known $2t$ values are evenly spaced (that is, when the elements of $J$ are in arithmetic progression) for classes of matrices satisfying certain row properties. These cases include Fourier $nimesn$ matrices where the arithmetic difference $k$ satisfies $gcd(n,k)=1$, and classes of Vandermonde matrices $V(x_1,x_2,ldots,x_n)$ (with $x_{i}eq0$) with arithmetic difference $k$ where the ratios $x_i/x_j$ for $ieqj$ are not $k^{th}$ roots of unity. The decoding algorithm has complexity $O(nt)$ and in some cases, including the Fourier matrix cases, the complexity is $O(t^2)$. 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 $C^{p}erp=E_j|jinJ$ with a decoding algorithm which finds $x$. This has applications to signal processing and compressed sensing.

Full work available at URL: https://arxiv.org/abs/1509.03784

zbMATH Keywords

signal processingcodescompressed sensingunderdetermined system

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Linear equations (linear algebraic aspects) (15A06) Communication theory (94A05)

Related Items (1)

Decoding algorithm as a moment problem related to the extended Lotka–Volterra system

This page was built for publication: Solving underdetermined systems with error-correcting codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q725952)