Abstract In large-scale applications including medical imaging, collocation differential equation solvers, and estimation with differential privacy, the underlying linear inverse problem can be reformulated as a streaming problem. In theory, the streaming problem can be effectively solved using memory-efficient, exponentially-converging streaming solvers. In special cases when the underlying linear inverse problem is finite-dimensional, streaming solvers can periodically evaluate the residual norm at a substantial computational cost. When the underlying system is infinite dimensional, streaming solver can only access noisy estimates of the residual. While such noisy estimates are computationally efficient, they are useful only when their accuracy is known. In this work, we rigorously develop a general family of computationally-practical residual estimators and their uncertainty sets for streaming solvers, and we demonstrate the accuracy of our methods on a number of large-scale linear problems. Thus, we further enable the practical use of streaming solvers for important classes of linear inverse problems.
more »
« less
A Novel Structure-Preserving Algorithm with Green’s Function Approach for Computing Band Structures of Photonic Quasicrystals
A novel bi-infinite approach to compute the band structures of 2D photonic superlattices with 1D quasicrystal sequences is devised. Leveraging strategically the bi-infinite characteristic, the approach first transforms the infinite-dimensional eigenvalue problem into a finite-dimensional nonlinear eigenvalue problem (NEVP) on a single cell for efficient numerical solution. Challengingly, the NEVP is built upon the solutions to two systems of cyclic nonlinear matrix equations (NMEs) that have to be solved repeatedly during iteratively solving the NEVP. The solutions are efficiently calculated by a newly developed highly efficient coalescing technique followed by a structure-preserving doubling algorithm. It is showed that the cost of coalescing is proportional to the logarithm of N, the length of the truncated quasicrystal sequence, which is significant as the cost of coalescing becomes more noticeable as N gets bigger for highly accurate simulations. Finally, through mathematical analysis, inclusion intervals for eigenvalue of interest are estimated so as to significantly narrow down the scope of search, and that significantly contributes to the overall efficiency of the approach, as the NEVP is nonlinear in nature and has to be solved iteratively.
more »
« less
- Award ID(s):
- 2407692
- PAR ID:
- 10707462
- Publisher / Repository:
- Global-Science Press
- Date Published:
- Journal Name:
- Communications in Computational Physics
- Volume:
- 39
- Issue:
- 1
- ISSN:
- 1815-2406
- Subject(s) / Keyword(s):
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
A spatially periodic structure of heterogeneous elastic rods that periodically oscillate along their axes is proposed as a time-modulated phononic crystal. Each rod is a bi-material cylinder, consisting of periodically distributed slices with significantly different elastic properties. The rods are imbedded in an elastic matrix. Using a plane wave expansion, it is shown that the dispersion equation for sound waves is obtained from the solutions of a quadratic eigenvalue problem over the eigenfrequency ω. The coefficients of the corresponding quadratic polynomial are represented by infinite matrices defined in the space spanned by the reciprocal lattice vectors, where elements depend on the velocity of translation motion of the rods and Bloch vector k. The calculated band structure exhibits both ω and k bandgaps. If a frequency gap overlaps with a momentum gap, a mixed gap is formed. Within a mixed gap, ω and k acquire imaginary parts. A method of analysis of the dispersion equation in complex ω−k space is proposed. As a result of the high elastic contrast between the materials in the bi-material rods, a substantial depth of modulation is achieved, leading to a large gap to midgap ratio for the frequency, momentum, and mixed bandgaps.more » « less
-
Shawe-Taylor, John (Ed.)Learning a function from a finite number of sampled data points (measurements) is a fundamental problem in science and engineering. This is often formulated as a minimum norm interpolation (MNI) problem, a regularized learning problem or, in general, a semi-discrete inverse problem (SDIP), in either Hilbert spaces or Banach spaces. The goal of this paper is to systematically study solutions of these problems in Banach spaces. We aim at obtaining explicit representer theorems for their solutions, on which convenient solution methods can then be developed. For the MNI problem, the explicit representer theorems enable us to express the infimum in terms of the norm of the linear combination of the interpolation functionals. For the purpose of developing efficient computational algorithms, we establish the fixed-point equation formulation of solutions of these problems. We reveal that unlike in a Hilbert space, in general, solutions of these problems in a Banach space may not be able to be reduced to truly finite dimensional problems (with certain infinite dimensional components hidden). We demonstrate how this obstacle can be removed, reducing the original problem to a truly finite dimensional one, in the special case when the Banach space is ℓ1(N).more » « less
-
Abstract Bi-stochastic normalization provides an alternative normalization of graph Laplacians in graph-based data analysis and can be computed efficiently by Sinkhorn–Knopp (SK) iterations. This paper proves the convergence of bi-stochastically normalized graph Laplacian to manifold (weighted-)Laplacian with rates, when $$n$$ data points are i.i.d. sampled from a general $$d$$-dimensional manifold embedded in a possibly high-dimensional space. Under certain joint limit of $$n \to \infty $$ and kernel bandwidth $$\epsilon \to 0$$, the point-wise convergence rate of the graph Laplacian operator (under 2-norm) is proved to be $$ O( n^{-1/(d/2+3)})$$ at finite large $$n$$ up to log factors, achieved at the scaling of $$\epsilon \sim n^{-1/(d/2+3)} $$. When the manifold data are corrupted by outlier noise, we theoretically prove the graph Laplacian point-wise consistency which matches the rate for clean manifold data plus an additional term proportional to the boundedness of the inner-products of the noise vectors among themselves and with data vectors. Motivated by our analysis, which suggests that not exact bi-stochastic normalization but an approximate one will achieve the same consistency rate, we propose an approximate and constrained matrix scaling problem that can be solved by SK iterations with early termination. Numerical experiments support our theoretical results and show the robustness of bi-stochastically normalized graph Laplacian to high-dimensional outlier noise.more » « less
-
We consider optimal experimental design (OED) for Bayesian nonlinear inverse problems governed by partial differential equations (PDEs) under model uncertainty. Specifically, we consider inverse problems in which, in addition to the inversion parameters, the governing PDEs include secondary uncertain parameters. We focus on problems with infinite-dimensional inversion and secondary parameters and present a scalable computational framework for optimal design of such problems. The proposed approach enables Bayesian inversion and OED under uncertainty within a unified framework. We build on the Bayesian approximation error (BAE) approach, to incorporate modeling uncertainties in the Bayesian inverse problem, and methods for A-optimal design of infinite-dimensional Bayesian nonlinear inverse problems. Specifically, a Gaussian approximation to the posterior at the maximuma posterioriprobability point is used to define an uncertainty aware OED objective that is tractable to evaluate and optimize. In particular, the OED objective can be computed at a cost, in the number of PDE solves, that does not grow with the dimension of the discretized inversion and secondary parameters. The OED problem is formulated as a binary bilevel PDE constrained optimization problem and a greedy algorithm, which provides a pragmatic approach, is used to find optimal designs. We demonstrate the effectiveness of the proposed approach for a model inverse problem governed by an elliptic PDE on a three-dimensional domain. Our computational results also highlight the pitfalls of ignoring modeling uncertainties in the OED and/or inference stages.more » « less
An official website of the United States government

