Learning the Mathematical Property for Designing Low Mutual Coherence Binary Sensing Matrices

Rekha; Santosh Singh; S. K. Neogy

cs.LGAug 13, 2026

Learning the Mathematical Property for Designing Low Mutual Coherence Binary Sensing Matrices

Authors: Rekha, Santosh Singh, S. K. Neogy

Organizations: Department of Mathematics, Shiv Nadar Institution of Eminence, Delhi, India. · Centre for Research on Economics and Data Analysis (CREDA), Indian Statistical Institute, New Delhi, India.

Abstract

In this research work, we are constructing the sensing matrix, which is essential for the success of the compressive sensing technique. We have chosen a learning-based technique for the construction of the sensing matrix. The novelty and uniqueness of the proposed technique is that it does not use any data set and also does not use a specific application. It uses the mathematical property/constraint for the construction of the sensing matrix for the perfect recovery of the signal. The perfect recovery of signals is an old and still very challenging problem in real-world applications. In late 2000, compressive sensing became a popular mathematical tool for the perfect recovery of sparse signals. The core of the compressive technique is the construction of the sensing matrix, which satisfies certain special properties such as restricted isometry property (RIP), null space property (NSP), and spark property (SP). All these properties are NP-hard problems and hence computationally challenging to solve. For all practical purposes, the construction of the sensing matrix needs to achieve low mutual coherence to achieve the perfect recovery of the signals. We have used a neural network for the construction of the sensing matrix, and this framework constructs a binary sensing matrix with low mutual coherence. The entries in the matrix are generated through a shared underlying rule. The proposed architecture is simple and does not use large-scale training data sets. Such uniqueness and novelty bring a drastic reduction in computational cost, and also, for the first time in literature, the use of a mathematical property for defining the loss function. In this proposed research work, the mutual coherence property has been used in the neural network framework. Such a neural network framework brings generality, robustness, and reduces storage requirements.

Explore similar work

Sep 1, 2025stat.ML

The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements

We consider the problem of support recovery for sparse binary signals from noisy linear measurements. For sparse Gaussian measurement matrices we identify sufficient conditions on the minimal sample size for maximum-likelihood recovery in the high-SNR regime

ds/p \to \infty

, where

p

denotes the signal dimension,

s

the number of non-zero components of the signal, and

d

the expected number of non-zero components per row of measurement. Combined with known lower bounds, this yields an information-theoretic threshold of order

s\log(p/s) / \log(ds/p)

, making explicit the price of measurement sparsity. In particular, we highlight a regime where the sample-complexity loss from measurement sparsity is logarithmic while the computational gain is nearly linear. Second, we study recovery after sparsifying an originally dense Gaussian design: the observations are generated from the dense design, while estimation uses an independently sparsified design and a rescaled response. In the proportional regime

s=αp

d=ψp

, we prove that, for every fixed target error level

δ

and every slack

\varepsilon>0

, a sample size of order

p/ψ^2

is sufficient for support recovery for arbitrarily small

ψ

Youssef Chaabouni, David Gamarnik

Sparse Recovery Sparsity Optimal Sample Complexity Noisy Data Sufficient Conditions

Ask PDF

Sep 15, 2026math.NA

Near-Optimal Nonconvex Matrix Completion

We study nonconvex methods for matrix completion, the problem of recovering a low-rank matrix from a subset of its entries. Convex methods achieve sample complexity linear in the matrix dimension and the rank, up to logarithmic factors, whereas global guarantees for commonly used nonconvex methods require a higher polynomial dependence on the rank. We close this gap by analyzing Riemannian gradient descent (RGD) and Riemannian Gauss--Newton (RGN) methods. For an

n\times n

matrix of rank

r

with incoherence parameter

μ

and condition number

κ

, the two methods achieve exact recovery with high probability from

O(μnr\log n\log(nκ))

and

O(μnr\log n\log(2μrκ))

observations, respectively. The methods use a multiscale residual initialization, while the analysis simultaneously controls the spectral error and incoherence. The resulting RGD iterates converge linearly, whereas RGN eventually converges Q-quadratically.

Jian-Feng Cai, Xiliang Lu, Juntao You

Tensor Completion Convex Optimization Sample Complexity

Ask PDF

Oct 28, 2025cs.IT

Robustness to Sparse Adversarial Corruption in Arbitrary Linear Measurements: Beyond Exact Recovery

Recovery from linear measurements under sparse adversarial corruption is typically formulated as an exact-recovery problem: one seeks structural conditions on

\mathbf{A}

(e.g., restricted isometry property) guaranteeing unique recovery of

\mathbf{x}^\star

from

\mathbf{y} = \mathbf{A}\mathbf{x}^\star + \mathbf{e}

with

\|\mathbf{e}\|_0 \leq q

. However, these guarantees provide no guidance once exact recovery fails. This limitation obscures simple robustness phenomena -- for instance, repeated rows in

\mathbf{A}

can preserve nontrivial information about

\mathbf{x}^\star

under sparse corruption. In this paper, we study what information about

\mathbf{x}^\star

can be \emph{uniformly} recovered from

\mathbf{y} = \mathbf{A}\mathbf{x}^\star + \mathbf{e}

for arbitrary

\mathbf{A}\in\mathbb{R}^{m\times n}

and \emph{any}

q

-sparse

\mathbf{e}

. We show that the robust information is precisely

\mathbf{x}^\star + \ker(\mathbf{U})

, where

\mathbf{U}

is the orthogonal projection onto the intersection of rowspaces of all submatrices of

\mathbf{A}

obtained by deleting

2q

rows. This clarifies how the row structure of

\mathbf{A}

governs whether a

q

-sparse corruption allows exact, partial, or only trivial recovery. We further prove every

\mathbf{x}

minimizing

\|\mathbf{y} - \mathbf{A} \mathbf{x}\|_0

belongs to

\mathbf{x}^\star + \ker(\mathbf{U})

, yielding a constructive approach to recover this set. For i.i.d. Gaussian matrices, we establish a sharp phase transition between exact and trivial recovery. We sketch two applications: robust network tomography and signal reconstruction from oversampled DCT.

Vishal Halder, Alexandre Reiffers-Masson, Abdeldjalil Aïssa-El-Bey +1

Sparse Recovery Adversarial Corruption 3D Gaussian Splatting

Ask PDF