Structured random sketching for PDE inverse problems

DOI10.1137/20M1310497MaRDI QIDQ5146630zbMATH OpenOpenAlexFDO

Authors Ke Chen, Qin Li, Kit Newton, Stephen J. Wright

Publication date 26 January 2021

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

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

zbMATH Keywords

inverse problempartial differential equationsrandom sketchingtensor

Mathematics Subject Classification ID

Numerical solutions to overdetermined systems, pseudoinverses (65F20) Randomized algorithms (68W20)

Abstract: For an overdetermined system $mathsfAmathsfxapproxmathsfb$ with $mathsfA$ and $mathsfb$ given, the least-square (LS) formulation $mi{n}_x,|mathsfAmathsfx-mathsfb{|}_2$ is often used to find an acceptable solution $mathsfx$. The cost of solving this problem depends on the dimensions of $mathsfA$, which are large in many practical instances. This cost can be reduced by the use of random sketching, in which we choose a matrix $mathsfS$ with fewer rows than $mathsfA$ and $mathsfb$, and solve the sketched LS problem $mi{n}_x,|mathsfS(mathsfAmathsfx-mathsfb){|}_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 $mathsfS$. When $mathsfA$ and $mathsfb$ arise from discretizations of a PDE-based inverse problem, tensor structure is often present in $mathsfA$ and $mathsfb$. For reasons of practical efficiency, $mathsfS$ should be designed to have a structure consistent with that of $mathsfA$. Can we claim similar approximation properties for the solution of the sketched LS problem with structured $mathsfS$ as for fully-random $mathsfS$? 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.

Recommendations

• Tensor-structured sketching for constrained least squares
• A statistical perspective on randomized sketching for ordinary least-squares
• A sketched finite element method for elliptic models
• Iterative Hessian sketch: fast and accurate solution approximation for constrained least-squares
• Randomized sketching algorithms for low-memory dynamic optimization

Cites work

• A fast randomized algorithm for overdetermined linear least-squares regression
• A Practical Randomized CP Tensor Decomposition
• A statistical perspective on algorithmic leveraging
• A statistical perspective on randomized sketching for ordinary least-squares
• Compressed matrix multiplication
• Electrical Impedance Tomography
• Electrical impedance tomography
• Extensions of Lipschitz mappings into a Hilbert space
• Faster least squares approximation
• Guarantees for the Kronecker fast Johnson-Lindenstrauss transform using a coherence and sampling argument
• Hanson-Wright inequality and sub-Gaussian concentration
• High-dimensional probability. An introduction with applications in data science
• Iterative Hessian sketch: fast and accurate solution approximation for constrained least-squares
• Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
• Optical tomography in medical imaging
• Random weighted projections, random quadratic forms and random eigenvectors
• Randomized Algorithms for Matrices and Data
• Randomized alternating least squares for canonical tensor decompositions: application to a PDE with random data
• Randomized interpolative decomposition of separated representations
• Randomized Sketches of Convex Programs With Sharp Guarantees
• Sketching as a tool for numerical linear algebra
• Stability of stationary inverse transport equation in diffusion scaling
• Subspace embeddings for the L ₁ -norm with applications

Cited in

(6)

• A data-scalable randomized misfit approach for solving large-scale PDE-constrained inverse problems
• Tensor-structured sketching for constrained least squares
• On unifying randomized methods for inverse problems
• Fast algorithms for least squares problems with Kronecker lower subsets
• Sketched and truncated polynomial Krylov subspace methods: matrix Sylvester equations
• Efficient randomized algorithms for fixed precision problem of approximate Tucker decomposition

This page was built for publication: Structured random sketching for PDE inverse problems

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