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

This paper proposes a novel learning-based framework for constructing binary sensing matrices with low mutual coherence for compressive sensing applications. The key innovation is that the proposed method learns directly from the mathematical property of mutual incoherence rather than from training data, making it fundamentally different from conventional data-driven deep learning approaches.

The paper addresses the challenge of designing effective sensing matrices for compressive sensing (CS), which enables recovery of sparse signals from reduced measurements. The sensing matrix plays a fundamental role in determining the accuracy and reliability of signal reconstruction. The paper notes that theoretical properties such as Restricted Isometry Property (RIP), Null Space Property (NSP), and Spark property are NP-hard to verify, making them computationally challenging. The authors therefore focus on the Mutual Incoherence Property (MIP), which is computationally tractable and can be evaluated efficiently.

The paper identifies three categories of existing sensing matrix designs:

1. Random matrices (Gaussian or Bernoulli ensembles): These satisfy theoretical conditions with high probability and are largely incoherent with most sparsifying bases, but require significant storage space and lead to high computational complexity due to their dense and unstructured nature.

2. Deterministic matrices: These aim to minimize mutual coherence through optimization problems, often using iterative algorithms. While they provide improved performance compared to random matrices, their construction procedures remain computationally expensive and mathematically complex.

3. Data-driven learned matrices: These jointly optimize sensing and reconstruction using large training datasets. However, they rely heavily on extensive training data and computationally intensive architectures, and primarily focus on data-driven optimization rather than explicitly enforcing theoretical properties required for compressive sensing.

The objective is to construct a binary sensing matrix Aθ ∈ RM×N with entries restricted to 1/√M, -1/√M, where columns are generated through a shared underlying rule. The optimization problem is formulated as:

min L(Aθ) subject to Aθ(i,j) ∈ 1/√M, -1/√M, with columns generated by shared-rule.

The proposed model uses a simple fully connected feedforward neural network with:

• Input layer (dimension M)

• Hidden dense layer with 128 neurons using ReLU activation

• Another fully connected layer with 64 neurons with linear activation

• Output layer applying Straight-Through Estimator (STE)-based sign function for binary constraint

• Normalization by 1/√M

Each column of the sensing matrix is generated by feeding latent vectors zj ∈ RM (sampled from a Gaussian distribution) through the network: aj = (1/√M)·sgn(Nθ(zj)). The same neural network with shared parameters θ generates all columns, with only the latent vector varying across columns.

Since maximum mutual coherence is non-differentiable, the authors propose a combined loss function with three components:

1. Lp-norm Loss: Lp-norm(Aθ) = (ΣGij p)(1/p) for i≠j, which approaches the maximum coherence as p→∞

2. LogSumExp Loss: LLogSum(Aθ) = (1/ξ)log(Σe(ξGij)) for i≠j, providing a smoother approximation to the maximum with stable gradients

3. Tight Frame Loss: Ltight(Aθ) = AAT - (N/M)I2F, encouraging the matrix to approach an equiangular tight frame structure

The total loss is: L(Aθ) = α1·Lp-norm(Aθ) + α2·LLogSum(Aθ) + α3·Ltight(Aθ), with weighting coefficients α1=3, α2=1, α3=0.5.

The model does not require large-scale training data. It learns from the incoherence property itself, feeding latent vectors sampled from a Gaussian distribution. The model was trained for 1000 epochs with learning rate 0.0001, using p=8 and ξ=30 for the loss function parameters.

• The loss function shows consistent decrease over iterations

• Maximum mutual coherence exhibits local fluctuations (reflecting switching of worst-case coherence pairs) but the overall envelope decreases progressively

• Average and total mutual coherence show smoother, strictly decreasing trends

The proposed method was compared with random Gaussian and Bernoulli matrices across different dimensions:

For M=64, N=128:

• Maximum coherence: Proposed ≈ 0.281 vs. Gaussian ≈ 0.481 vs. Bernoulli ≈ 0.496

• Average coherence: Proposed ≈ 0.091 vs. Gaussian ≈ 0.099 vs. Bernoulli ≈ 0.098

• Total coherence: Proposed ≈ 200.58 vs. Gaussian ≈ 256.23 vs. Bernoulli ≈ 253.34

For M=64, N=256:

• Maximum coherence: Proposed ≈ 0.343 vs. Gaussian ≈ 0.501 vs. Bernoulli ≈ 0.528

• Average coherence: Proposed ≈ 0.092 vs. Gaussian ≈ 0.099 vs. Bernoulli ≈ 0.098

• Total coherence: Proposed ≈ 854.37 vs. Gaussian ≈ 1022.83 vs. Bernoulli ≈ 1019.58

For M=128, N=256:

• Maximum coherence: Proposed ≈ 0.250 vs. Gaussian ≈ 0.368 vs. Bernoulli ≈ 0.368

• Average coherence: Proposed ≈ 0.068 vs. Gaussian ≈ 0.070 vs. Bernoulli ≈ 0.070

• Total coherence: Proposed ≈ 441.97 vs. Gaussian ≈ 510.52 vs. Bernoulli ≈ 509.27

• Gram matrix heatmaps show significantly weaker off-diagonal entries for learned matrices compared to initial matrices

• Histograms of off-diagonal Gram entries show the proposed method's distribution is more concentrated around zero with considerably shorter tails than random matrices

1. No training data required: The model learns from the mathematical property rather than data, improving generalization

2. Simple architecture: Only a few layers with 128 and 64 neurons, reducing computational complexity

3. Binary nature: Entries restricted to 1/√M, -1/√M reduce storage requirements and enable hardware-efficient implementation

4. Shared rule generation: All columns generated through the same network parameters, requiring only compact storage of network parameters

5. Property-driven learning: Novel approach using mathematical property for defining the loss function, applicable across multiple disciplines

The paper demonstrates that the proposed property-driven learning framework effectively constructs binary sensing matrices with substantially reduced maximum, average, and total mutual coherence compared to conventional random sensing matrices. The approach offers an efficient, scalable, and practical solution for compressive sensing applications, particularly in resource-constrained environments, by simultaneously achieving low storage complexity, low mutual coherence, simple construction, and lightweight learning.

Improvements to AI Systems:

1. Property-Driven Optimization without Training Data

• Replace data-hungry supervised learning with loss functions derived directly from mathematical properties (e.g., mutual coherence, tight frame constraints).

• Enables AI systems to optimize for provable theoretical guarantees (e.g., low coherence) rather than relying on empirical data distributions, improving generalization to unseen signal classes.

2. Binary Constraint Handling via Straight-Through Estimator (STE)

• Integrate STE-based sign functions into neural network outputs to enforce hard binary constraints (e.g., +1/√M, -1/√M) during training.

• Allows AI systems to generate hardware-friendly, storage-efficient solutions (e.g., sensing matrices) while maintaining gradient flow for backpropagation.

3. Scalable Shared-Rule Generation

• Use a single neural network with shared parameters to generate all columns of a structured matrix, conditioned on latent vectors.

• Reduces memory footprint and enables compact representation of large matrices, making AI systems deployable in resource-constrained edge devices.

4. Multi-Objective Loss with Smooth Approximations

• Combine non-differentiable objectives (e.g., max coherence) with smooth surrogates like LogSumExp and Lp-norm losses, plus a tight frame regularizer.

• Improves training stability and convergence by balancing global worst-case metrics with average-case behavior, leading to more robust optimization.

5. Coherence-Aware Regularization for Reconstruction Models

• Apply the proposed loss components (e.g., Lp-norm, LogSumExp, tight frame) as regularizers in autoencoders or deep unfolding networks for compressive sensing.

• Enhances reconstruction quality by explicitly minimizing mutual coherence during training, reducing artifacts from correlated measurements.

6. Latent Space Sampling for Deterministic Matrix Design

• Sample latent vectors from a Gaussian distribution to generate diverse but coherently structured matrices, avoiding exhaustive search or manual design.

• Enables AI systems to explore a continuous space of near-optimal binary matrices, facilitating rapid prototyping for different dimensions (M, N).

Capabilities of the Improved AI System:

• Data-Free Compressive Sensing: Designs optimal sensing matrices without any training data, making it adaptable to arbitrary sparse signal domains (e.g., images, audio, medical signals).

• Hardware-Efficient Deployment: Produces binary matrices with minimal storage (only network parameters) and low computational cost, suitable for IoT sensors, FPGA implementations, and real-time processing.

• Provable Performance: Achieves significantly lower maximum, average, and total coherence than random matrices (e.g., max coherence reduced by 40–50%), improving worst-case reconstruction guarantees.

• Flexible Dimensional Scaling: Generates matrices for various M and N configurations (e.g., 64×128, 64×256, 128×256) with consistent coherence reduction, enabling adaptive sensing systems.

• Transferable Optimization: The property-driven loss framework can be repurposed for other matrix design problems (e.g., dictionary learning, graph adjacency matrices, error-correcting codes) where incoherence or tight frames are beneficial.