Special Events and Conferences

Title: Randomized algorithms for solving inverse problems in X-ray science

Description: Inverse problems map model parameters to observed data, yet current large-scale methods often rely on “one-sided sampling”—either subsampling the data or coarsening the parameter space—thus overlooking correlations between these two domains. In this work, we propose structure-informed randomized sampling in both parameter and data spaces simultaneously to reduce the effective problem size while maintaining acceptable solution accuracy. We focus on two DOE-relevant applications: (1) limited-angle tomography, a linear inverse problem complicated by hardware constraints, radiation dosage limitations, and incomplete projections, and (2) blind ptychography, a nonlinear, nonconvex phase retrieval task that involves massive datasets and unknown system parameters.

More detailed description of the applications:

• (1) limited angle tomography: Tomography, as the most representative linear inverse problem, has become increasingly complicated over the years due to improved hardware, as well as more complicated experimental environments. In principle, tomographic reconstruction requires and ingests projections made from a half-circle of angles. However, because of hardware conditions, radiation dose, or the state of the object being imaged, it is typically difficult or impossible to obtain a complete set of projections with full rotations and ideal experimental configurations in practice. For instance, one may encounter a missing wedge in electron tomography, a limited range of angles in laminography, or station instability in a portable CT machine.

• (2) Phase retrieval is a well-known problem in mathematics and continues to be a subject of research because of the challenges presented by its innate nonlinearity and nonconvexity. We will particularly focus on one of the most challenging types of phase retrieval, blind ptychography. One main additional challenge of blind ptychography is its large computational cost caused by massive volumes of data.

Prerequisites:

• Solving least square problems with incomplete data, or sparse data
• Randomized sketching or projection
• CUR decomposition, and other low-rank techniques
• Randomized SVD

Project leaders:

• Lead: Sherry Li, Lawrence Berkeley National Laboratory
• Co-Lead: Wendy Di, Argonne National Laboratory

Title: Structure-aware randomization for linear algebra

Description: Efficient linear algebra is critical in scientific simulations of quantum phenomena, turbulent flow, multiscale phenomena, etc. Randomized algorithms hold the promise of acceleration, but significant work remains in designing algorithms that leverage high-level problem structures and data layout considerations. We will explore the design of randomized algorithms that address such problems. For example, in certain quantum applications, it can be useful to perform a variant of pivoted QR where a pivot is a choice among predefined column blocks, rather than a choice among individual columns. We propose to explore such a scenario in this project.

Prerequisites:

• Linear algebra,
• Programming (MATLAB or Python)

Project leaders:

• Lead: Tammy Kolda, Math Sci.ai
• Co-Lead: Riley Murray, Sandia

Title: Randomized Krylov Methods for Large-scale Inverse Problems

Descirption: This project will consider new randomized Krylov methods for solving large-scale inverse problems. There have been many recent advances in incorporating randomization within well-established iterative methods for numerical linear algebra, but the extension to inverse problems has not been fully explored. We will develop and investigate various approaches towards establishing new efficient randomized solvers for linear inverse problems, including iterative methods with sketched inner products, sketch-and-solve methods for solving projected problems, and prior informed sketching for Bayesian inverse problems, focusing on the interplay between randomization and regularization. Examples from image processing and tomographic reconstruction will be used to compare our newly developed methods with other deterministic and randomized optimization methods.

Prerequisites:

• Linear algebra,
• Krylov methods,
• MATLAB programming

Project leaders:

• Lead: Julianne Chung (Emory University)
• Co-Lead: Silvia Gazzola (University of Pisa, Italy)

Title: Randomization in transformer models

Description: Randomization techniques have been successfully applied in scientific computing and data analysis to address various problems, including low-rank matrix approximation, solving linear systems and eigenvalue problems using Krylov subspace methods, and tackling the column subset selection problem. In this project, we investigate the use of randomization in transformer models, widely used in natural language processing and machine learning. We will focus on key problems related to the attention mechanism, which computes pairwise interactions between all input tokens and typically scales quadratically with respect to the sequence length. This computational bottleneck motivates the exploration of randomized algorithms to accelerate computations while maintaining accuracy.

Prerequisites:

• Linear algebra,
• MATLAB, Python, or Julia programming

Project leaders:

• Lead: Laura Grigori (EPFL)
• Co-Lead: Alice Cortinovis (University of Pisa)
• Co-Lead: Michel Fabrice Serret (PSI Paul Scherrer Institute)