Researcher profile

Laurent Demanet

Laurent Demanet contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate

math.NA Numerical Analysis Information Theory math.IT math.OC physics.geo-ph Machine Learning math.PR math.ST physics.comp-ph physics.data-an Statistics Theory

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author

9works

0followers

12topics

4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

Redatuming physical systems using symmetric autoencoders

This paper considers physical systems described by hidden states and indirectly observed through repeated measurements corrupted by unmodeled nuisance parameters. A network-based representation learns to disentangle the coherent information (relative to the state) from the incoherent nuisance information (relative to the sensing). Instead of physical models, the representation uses symmetry and stochastic regularization to inform an autoencoder architecture called SymAE. It enables redatuming, i.e., creating virtual data instances where the nuisances are uniformized across measurements.

preprint2019arXiv

L-Sweeps: A scalable, parallel preconditioner for the high-frequency Helmholtz equation

We present the first fast solver for the high-frequency Helmholtz equation that scales optimally in parallel, for a single right-hand side. The L-sweeps approach achieves this scalability by departing from the usual propagation pattern, in which information flows in a 180 degree cone from interfaces in a layered decomposition. Instead, with L-sweeps, information propagates in 90 degree cones induced by a checkerboard domain decomposition (CDD). We extend the notion of accurate transmission conditions to CDDs and introduce a new sweeping strategy to efficiently track the wave fronts as they propagate through the CDD. The new approach decouples the subdomains at each wave front, so that they can be processed in parallel, resulting in better parallel scalability than previously demonstrated in the literature. The method has an overall O((N/p) log w) empirical run-time for N=n^d total degrees-of-freedom in a d-dimensional problem, frequency w, and p=O(n) processors. We introduce the algorithm and provide a complexity analysis for our parallel implementation of the solver. We corroborate all claims in several two- and three-dimensional numerical examples involving constant, smooth, and discontinuous wave speeds.

preprint2013arXiv

A parallel butterfly algorithm

The butterfly algorithm is a fast algorithm which approximately evaluates a discrete analogue of the integral transform \int K(x,y) g(y) dy at large numbers of target points when the kernel, K(x,y), is approximately low-rank when restricted to subdomains satisfying a certain simple geometric condition. In d dimensions with O(N^d) quasi-uniformly distributed source and target points, when each appropriate submatrix of K is approximately rank-r, the running time of the algorithm is at most O(r^2 N^d log N). A parallelization of the butterfly algorithm is introduced which, assuming a message latency of αand per-process inverse bandwidth of β, executes in at most O(r^2 N^d/p log N + βr N^d/p + α)log p) time using p processes. This parallel algorithm was then instantiated in the form of the open-source DistButterfly library for the special case where K(x,y)=exp(i Φ(x,y)), where Φ(x,y) is a black-box, sufficiently smooth, real-valued phase function. Experiments on Blue Gene/Q demonstrate impressive strong-scaling results for important classes of phase functions. Using quasi-uniform sources, hyperbolic Radon transforms and an analogue of a 3D generalized Radon transform were respectively observed to strong-scale from 1-node/16-cores up to 1024-nodes/16,384-cores with greater than 90% and 82% efficiency, respectively.

preprint2013arXiv

Eventual linear convergence of the Douglas Rachford iteration for basis pursuit

We provide a simple analysis of the Douglas-Rachford splitting algorithm in the context of $\ell^1$ minimization with linear constraints, and quantify the asymptotic linear convergence rate in terms of principal angles between relevant vector spaces. In the compressed sensing setting, we show how to bound this rate in terms of the restricted isometry constant. More general iterative schemes obtained by $\ell^2$-regularization and over-relaxation including the dual split Bregman method are also treated, which answers the question how to choose the relaxation and soft-thresholding parameters to accelerate the asymptotic convergence rate. We make no attempt at characterizing the transient regime preceding the onset of linear convergence.

preprint2013arXiv

Stable optimizationless recovery from phaseless linear measurements

We address the problem of recovering an n-vector from m linear measurements lacking sign or phase information. We show that lifting and semidefinite relaxation suffice by themselves for stable recovery in the setting of m = O(n log n) random sensing vectors, with high probability. The recovery method is optimizationless in the sense that trace minimization in the PhaseLift procedure is unnecessary. That is, PhaseLift reduces to a feasibility problem. The optimizationless perspective allows for a Douglas-Rachford numerical algorithm that is unavailable for PhaseLift. This method exhibits linear convergence with a favorable convergence rate and without any parameter tuning.

preprint2013arXiv

Super-resolution via superset selection and pruning

We present a pursuit-like algorithm that we call the "superset method" for recovery of sparse vectors from consecutive Fourier measurements in the super-resolution regime. The algorithm has a subspace identification step that hinges on the translation invariance of the Fourier transform, followed by a removal step to estimate the solution's support. The superset method is always successful in the noiseless regime (unlike L1-minimization) and generalizes to higher dimensions (unlike the matrix pencil method). Relative robustness to noise is demonstrated numerically.

preprint2013arXiv

Velocity estimation via registration-guided least-squares inversion

This paper introduces an iterative scheme for acoustic model inversion where the notion of proximity of two traces is not the usual least-squares distance, but instead involves registration as in image processing. Observed data are matched to predicted waveforms via piecewise-polynomial warpings, obtained by solving a nonconvex optimization problem in a multiscale fashion from low to high frequencies. This multiscale process requires defining low-frequency augmented signals in order to seed the frequency sweep at zero frequency. Custom adjoint sources are then defined from the warped waveforms. The proposed velocity updates are obtained as the migration of these adjoint sources, and cannot be interpreted as the negative gradient of any given objective function. The new method, referred to as RGLS, is successfully applied to a few scenarios of model velocity estimation in the transmission setting. We show that the new method can converge to the correct model in situations where conventional least-squares inversion suffers from cycle-skipping and converges to a spurious model.

preprint2012arXiv

Sublinear randomized algorithms for skeleton decompositions

Let $A$ be a $n$ by $n$ matrix. A skeleton decomposition is any factorization of the form $CUR$ where $C$ comprises columns of $A$, and $R$ comprises rows of $A$. In this paper, we consider uniformly sampling $ł\simeq k \log n$ rows and columns to produce a skeleton decomposition. The algorithm runs in $O(ł^3)$ time, and has the following error guarantee. Let $\norm{\cdot}$ denote the 2-norm. Suppose $A\simeq X B Y^T$ where $X,Y$ each have $k$ orthonormal columns. Assuming that $X,Y$ are incoherent, we show that with high probability, the approximation error $\norm{A-CUR}$ will scale with $(n/ł)\norm{A-X B Y^T}$ or better. A key step in this algorithm involves regularization. This step is crucial for a nonsymmetric $A$ as empirical results suggest. Finally, we use our proof framework to analyze two existing algorithms in an intuitive way.

preprint2011arXiv

Matrix probing and its conditioning

When a matrix A with n columns is known to be well approximated by a linear combination of basis matrices B_1,..., B_p, we can apply A to a random vector and solve a linear system to recover this linear combination. The same technique can be used to recover an approximation to A^-1. A basic question is whether this linear system is invertible and well-conditioned. In this paper, we show that if the Gram matrix of the B_j's is sufficiently well-conditioned and each B_j has a high numerical rank, then n {proportional} p log^2 n will ensure that the linear system is well-conditioned with high probability. Our main application is probing linear operators with smooth pseudodifferential symbols such as the wave equation Hessian in seismic imaging. We demonstrate numerically that matrix probing can also produce good preconditioners for inverting elliptic operators in variable media.

Laurent Demanet

Quick read

Decide how to stay connected

How to connect with this researcher

Open a focused conversation when the fit is right

See the researcher in context

Building this graph slice

9 published item(s)

Redatuming physical systems using symmetric autoencoders

L-Sweeps: A scalable, parallel preconditioner for the high-frequency Helmholtz equation

A parallel butterfly algorithm

Eventual linear convergence of the Douglas Rachford iteration for basis pursuit

Stable optimizationless recovery from phaseless linear measurements

Super-resolution via superset selection and pruning

Velocity estimation via registration-guided least-squares inversion

Sublinear randomized algorithms for skeleton decompositions

Matrix probing and its conditioning