Pseudo-inverses of difference matrices and their application to sparse signal approximation

Gerlind Plonka, Sebastian Hoffmann, Joachim Weickert

Abstract

This paper presents a novel approach to sparse signal reconstruction (inpainting) by deriving explicit, closed-form expressions for the Moore-Penrose pseudo-inverses of symmetric difference matrices. By interpreting the columns of these pseudo-inverses as a dictionary of discrete Green's functions, the authors utilize Orthogonal Matching Pursuit (OMP) to achieve high-quality signal approximation from minimal data points. The work establishes a theoretical bridge between partial differential equations (PDEs) and classical spline interpolation theory.

Introduction

Sparse data interpolation, or inpainting, is the process of reconstructing a full signal or image from a highly undersampled set of known data points. This task is typically framed as a regularization problem where the underlying signal is assumed to be smooth, often satisfying a specific differential equation such as the Laplace or biharmonic equation.

Two primary challenges hinder this process: the NP-hard nature of selecting optimal sampling points and the inherent singularity of the difference matrices used to represent differential operators. Because operators like the discrete Laplacian possess a null space (e.g., constant signals), they cannot be inverted through standard means. This paper addresses these challenges by providing a rigorous linear algebra framework for generalized inversion and point selection.

Mathematical Framework and Methods

Explicit Pseudo-Inverses

The authors provide a general theorem to compute the Moore-Penrose inverse ($L^+$) for any symmetric difference matrix of rank $N-1$. They derive exact formulas for the components of these inverses specifically for the discrete Laplacian and biharmonic operators. These derivations cover both periodic and Neumann (reflecting) boundary conditions, eliminating the need for computationally expensive and numerically unstable numerical inversions of large matrices.

Dictionary Construction and OMP

A key insight of the paper is that the columns of these pseudo-inverses function as discrete Green’s functions. In a diffusion process, these columns represent the "influence" of a single data point. By treating these columns as a dictionary of basis functions (atoms), the inpainting problem is reformulated as a sparse approximation problem: $u = L^+g$, where $g$ is a sparse vector representing the known data values.

To solve the point selection problem, the authors employ Orthogonal Matching Pursuit (OMP). This greedy algorithm iteratively selects the dictionary atoms—and by extension, the sample points—that best explain the remaining energy in the signal. This approach simplifies the selection process compared to previous heuristic strategies.

The paper establishes a deep connection between PDE-based inpainting and classical approximation theory. The authors prove that:

  • Inpainting using the Laplacian operator is mathematically equivalent to linear spline interpolation with free knots.
  • Inpainting using the biharmonic operator corresponds to cubic spline interpolation.

This equivalence provides a solid theoretical foundation for why these operators are effective at capturing the underlying structure of smooth signals.

Experimental Results

The proposed method was evaluated on synthetic 1D signals (length $N=256$). Using only 13 points—representing approximately 5% of the original data—the method achieved significant reconstruction accuracy:

  • Reconstruction Quality: The method yielded Peak Signal-to-Noise Ratios (PSNR) ranging from 23.21 to 25.78 dB.
  • Operator Performance: While the biharmonic operator is theoretically smoother, the discrete Laplacian (linear splines) often performed better on signals with sharp transitions, as the biharmonic operator tended to over-smooth these features.
  • Boundary Conditions: Homogeneous Neumann boundary conditions outperformed periodic conditions in 75% of the test cases. This suggests that Neumann conditions are better suited for real-world signals that do not exhibit perfect periodicity at their boundaries.

Conclusion and Future Work

This research provides a computationally efficient and theoretically grounded framework for sparse signal approximation. By providing closed-form solutions for pseudo-inverses, the authors enable the use of OMP for optimal point selection in inpainting tasks.

However, the current scope is limited to one-dimensional signals. Future research will focus on extending these explicit components to 2D grids for image processing applications. Additionally, while the OMP approach is efficient, further work is needed to strictly enforce the "solvability condition" ($1^T g = 0$) within the greedy selection process to improve the robustness of the reconstruction.

Summary updated

Abstract

We derive new explicit expressions for the components of Moore-Penrose inverses of symmetric difference matrices. These generalized inverses are applied in a new regularization approach for scattered data interpolation based on partial differential equations. The columns of the Moore-Penrose inverse then serve as elements of a dictionary that allow a sparse signal approximation. In order to find a set of suitable data points for signal representation we apply the orthogonal patching pursuit (OMP) method.
BibTeX
@inproceedings{plonka2016pseudo,
  author = {Gerlind Plonka and Sebastian Hoffmann and Joachim Weickert},
  title = {{Pseudo-inverses of difference matrices and their application to sparse signal approximation}},
  booktitle = {Linear},
  year = {2016},
  doi = {10.1016/j.laa.2016.03.033},
}
Figure