Structured Random Sketching for PDE Inverse Problems

Ke Chen, Qin Li, Kit Newton, Stephen J. WrightSIAM Journal on Matrix Analysis and Applications 2020 · DOI · OpenReview

TL;DR

This paper introduces a new method for efficiently solving large-scale inverse problems arising from partial differential equations (PDEs). By exploiting the inherent tensor structure of these problems, their "structured random sketching" technique significantly reduces computational cost while maintaining high accuracy, outperforming standard methods.

What Problem Does This Paper Address?

Many scientific and engineering fields rely on solving inverse problems, which often involve large, overdetermined linear systems of the form $Ax \approx b$. Finding the least-squares solution $x^*$ for these systems can be computationally prohibitive when $A$ is massive. Random sketching offers a way to reduce the problem size by projecting $A$ and $b$ onto a smaller subspace using a sketching matrix $S$. However, for inverse problems derived from PDEs, the matrix $A$ often possesses a specific tensor structure. Standard random sketching methods don't leverage this structure, leading to inefficiencies. This paper addresses this gap by developing structured random sketching techniques that are tailored to the tensor structure of PDE-derived inverse problems, aiming for both computational efficiency and accuracy.

Methods

The core of this paper is the development of "structured random sketching" matrices. Instead of using generic random matrices, the authors design sketching matrices $S$ that mirror the tensor structure of the problem's matrix $A$.

  • Tensor Structure: The paper assumes that the matrix $A$ can be represented as a Khatri-Rao product of two smaller matrices, $A = F \otimes G$, and that the right-hand side vector $b$ also shares this structure. This tensor structure arises naturally from the discretization of PDE-based inverse problems, where solutions often involve products of functions derived from forward and adjoint equations.
  • Structured Sketching Matrices: Two types of structured sketching matrices are proposed:
  • Case 1: $S = P \otimes Q$, where $P$ and $Q$ are independent scaled Gaussian matrices. This approach sketches the components of the tensor structure independently.
  • Case 2: $S$ is constructed from random vectors $p_i$ and $q_i$ as $S_{i,:} = p_i^T \otimes q_i^T$. This method offers more randomness by not reusing components as in Case 1.
  • (ε, δ)-l² Embedding: The theoretical foundation relies on the concept of an (ε, δ)-l² embedding. A matrix $S$ is an (ε, δ)-l² embedding of a matrix $\bar{A}$ if it preserves the norm of vectors in the range space of $\bar{A}$ within an accuracy of ε with probability at least 1-δ. The paper proves that their structured sketching matrices satisfy this property for the tensor-structured matrices.
  • Theoretical Analysis: The authors derive bounds on the number of rows ($r$) required for the sketching matrix $S$ to achieve a certain accuracy (ε) with a given confidence level (δ). These bounds are shown to be independent of the ambient dimension ($n$) of the problem, which is crucial for large-scale applications.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and numerical experiments using synthetically generated matrices and a simulated Electrical Impedance Tomography (EIT) problem.

Key Insights and Ideas

  • Exploiting Structure is Key: The most significant insight is that by explicitly designing sketching matrices to match the tensor structure of PDE-derived inverse problems, one can achieve high accuracy with significantly fewer sketch rows ($r$) compared to unstructured methods.
  • Independence from Ambient Dimension: The derived bounds on $r$ are independent of the large ambient dimension $n$. This is a critical advantage for problems where $n$ can be extremely large (even infinite in theory), as it means the sketching cost doesn't scale with the problem's original size.
  • Two Structured Approaches: The paper presents two distinct structured sketching strategies (Case 1 and Case 2), each with slightly different theoretical bounds and practical performance characteristics. Case 2 generally shows better or comparable performance to unstructured Gaussian sketching.
  • Theoretical Guarantees: The work provides rigorous theoretical guarantees (in terms of (ε, δ)-l² embedding) for the accuracy of the sketched solutions, linking the number of sketch rows to the desired precision and confidence.

Key Results

  • Theoretical Bounds: The paper derives bounds on the number of rows $r$ for structured sketching matrices (Case 1 and Case 2) that ensure an (ε, δ)-l² embedding of the tensor-structured matrix $A$. These bounds depend on parameters like ε, δ, and the number of unknowns $p$, but crucially, not on the ambient dimension $n$.
  • Numerical Performance:
    • General Tensor Matrices: Experiments show that both Case 1 and Case 2 sketching strategies achieve accuracy comparable to or better than unstructured Gaussian sketching, especially as $r$ increases. Case 2 often performs slightly better.
  • Electrical Impedance Tomography (EIT): For a simulated EIT problem, the structured sketching methods (especially Case 2) successfully reconstruct the conductivity function, performing comparably to unstructured Gaussian sketching and outperforming Case 1.
  • Dependence on Parameters: Numerical results confirm the theoretical predictions that accuracy improves with increasing $r$ and is largely independent of $n$. The dependence on $p$ appears to be better than predicted by the theoretical bounds.

Limitations and Future Work

  • Optimality of Bounds: The authors acknowledge that the derived bounds on $r$ may not be optimal and that further understanding of quartic powers of Gaussian random variables is needed for tighter bounds.
  • Constant Factors: While the bounds are independent of $n$, the constant factors in the bounds can be large, especially for Case 1. The paper focuses on demonstrating the dependence on key parameters rather than optimizing these constants.
  • Future Research: The paper suggests future work could explore optimizing the constants in the bounds and investigating other tensor structures or sketching strategies. The observed linear dependence on $p$ in numerical results, which is better than the theoretical predictions, also warrants further investigation.

Summary updated

Abstract

For an overdetermined system ${A}{x} \approx {b}$ with ${A}$ and ${b}$ given, the least-squares (LS) formulation $\min_x \, \|{A}{x}-{b}\|_2$ is often used to find an acceptable solution ${x}$. The cost of solving this problem depends on the dimensions of ${A}$, which are large in many practical instances. This cost can be reduced by the use of random sketching, in which we choose a matrix ${S}$ with many fewer rows than ${A}$ and ${b}$ and solve the sketched LS problem $\min_x \, \|{S}({A} {x}-{b})\|_2$ to obtain an approximate solution to the original LS problem. Significant theoretical and practical progress has been made in the last decade in designing the appropriate structure and distribution for the sketching matrix ${S}$. When ${A}$ and ${b}$ arise from discretizations of a PDE-based inverse problem, tensor structure is often present in ${A}$ and ${b}$. For reasons of practical efficiency, ${S}$ should be designed to have a structure consistent with that of ${A}$. Can we claim similar approximation properties for the solution of the sketched LS problem with structured ${S}$ as for fully random ${S}$? We give estimates that relate the quality of the solution of the sketched LS problem to the size of the structured sketching matrices for two different structures. Our results are among the first known for random sketching matrices whose structure is suitable for use in PDE inverse problems.
BibTeX
@article{chen2020structured,
  author = {Ke Chen and Qin Li and Kit Newton and Stephen J. Wright},
  title = {{Structured Random Sketching for PDE Inverse Problems}},
  journal = {SIAM Journal on Matrix Analysis and Applications},
  year = {2020},
  doi = {10.1137/20m1310497},
}
Figure