An official website of the United States government
The CP tensor decomposition is used in applications such as machine learning and signal processing to discover latent low-rank structure in multidimensional data. Computing a CP decomposition via an alternating least squares (ALS) method reduces the problem to several linear least squares problems. The standard way to solve these linear least squares subproblems is to use the normal equations, which inherit special tensor structure that can be exploited for computational efficiency. However, the normal equations are sensitive to numerical ill-conditioning, which can compromise the results of the decomposition. In this paper, we develop versions of the CP-ALS algorithm using the QR decomposition and the singular value decomposition, which are more numerically stable than the normal equations, to solve the linear least squares problems. Our algorithms utilize the tensor structure of the CP-ALS subproblems efficiently, have the same complexity as the standard CP-ALS algorithm when the input is dense and the rank is small, and are shown via examples to produce more stable results when ill-conditioning is present. Our MATLAB implementation achieves the same running time as the standard algorithm for small ranks, and we show that the new methods can obtain lower approximation error.
more »
« less
Joint inversion of compact operators
Abstract Joint inversion of multiple data types was studied as early as 1975 in [K. Vozoff and D. L. Jupp,Joint inversion of geophysical data,Geophys. J. Internat. 42 1975, 3, 977–991],where the authors used the singular value decomposition to determine the degree of ill-conditioning of joint inverse problems. The authors demonstrated in several examples that combining two physical models in a joint inversion, and by effectively stacking discrete linear models, improved the conditioning as compared to individual inversions. This work extends the notion of using the singular value decomposition to determine the conditioning of discrete joint inversion to using the singular value expansion to determine the well-posedness of joint operators. We provide a convergent technique for approximating the singular values of continuous joint operators. In the case of self-adjoint operators, we give an algebraic expression for the joint singular values in terms of the singular values of the individual operators. This expression allows us to show that while rare, there are situations where ill-posedness may be not improved through joint inversion and in fact can degrade the conditioning of an individual inversion. The expression also quantifies the benefits of including repeated measurements in an inversion. We give an example of joint inversion with two moderately ill-posed Green’s function solutions, and quantify the improvement over individual inversions. This work provides a framework in which to identify data types that are advantageous to combine in a joint inversion.
more »
« less
- Award ID(s):
- 1720472
- PAR ID:
- 10188169
- Date Published:
- Journal Name:
- Journal of Inverse and Ill-posed Problems
- Volume:
- 28
- Issue:
- 1
- ISSN:
- 0928-0219
- Page Range / eLocation ID:
- 105 to 118
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)Abstract Randomized methods can be competitive for the solution of problems with a large matrix of low rank. They also have been applied successfully to the solution of large-scale linear discrete ill-posed problems by Tikhonov regularization (Xiang and Zou in Inverse Probl 29:085008, 2013). This entails the computation of an approximation of a partial singular value decomposition of a large matrix A that is of numerical low rank. The present paper compares a randomized method to a Krylov subspace method based on Golub–Kahan bidiagonalization with respect to accuracy and computing time and discusses characteristics of linear discrete ill-posed problems that make them well suited for solution by a randomized method.more » « less
-
The purpose of this work is to discuss the well-posedness theory of singular vortex patches. Our main results are of two types: well-posedness and ill-posedness. On the well-posedness side, we show that globally m m -fold symmetric vortex patches with corners emanating from the origin are globally well-posed in natural regularity classes as long as m ≥ 3. m\geq 3. In this case, all of the angles involved solve a closed ODE system which dictates the global-in-time dynamics of the corners and only depends on the initial locations and sizes of the corners. Along the way we obtain a global well-posedness result for a class of symmetric patches with boundary singular at the origin, which includes logarithmic spirals. On the ill-posedness side, we show that any other type of corner singularity in a vortex patch cannot evolve continuously in time except possibly when all corners involved have precisely the angle π 2 \frac {\pi }{2} for all time. Even in the case of vortex patches with corners of angle π 2 \frac {\pi }{2} or with corners which are only locally m m -fold symmetric, we prove that they are generically ill-posed. We expect that in these cases of ill-posedness, the vortex patches actually cusp immediately in a self-similar way and we derive some asymptotic models which may be useful in giving a more precise description of the dynamics. In a companion work from 2020 on singular vortex patches, we discuss the long-time behavior of symmetric vortex patches with corners and use them to construct patches on R 2 \mathbb {R}^2 with interesting dynamical behavior such as cusping and spiral formation in infinite time.more » « less
-
The focusing inversion of gravity and magnetic potential-field data using the randomized singular value decomposition (RSVD) method is considered. This approach facilitates tackling the computational challenge that arises in the solution of the inversion problem that uses the standard and accurate approximation of the integral equation kernel. We have developed a comprehensive comparison of the developed methodology for the inversion of magnetic and gravity data. The results verify that there is an important difference between the application of the methodology for gravity and magnetic inversion problems. Specifically, RSVD is dependent on the generation of a rank [Formula: see text] approximation to the underlying model matrix, and the results demonstrate that [Formula: see text] needs to be larger, for equivalent problem sizes, for the magnetic problem compared to the gravity problem. Without a relatively large [Formula: see text], the dominant singular values of the magnetic model matrix are not well approximated. We determine that this is due to the spectral properties of the matrix. The comparison also shows us how the use of the power iteration embedded within the randomized algorithm improves the quality of the resulting dominant subspace approximation, especially in magnetic inversion, yielding acceptable approximations for smaller choices of [Formula: see text]. Further, we evaluate how the differences in spectral properties of the magnetic and gravity input matrices also affect the values that are automatically estimated for the regularization parameter. The algorithm is applied and verified for the inversion of magnetic data obtained over a portion of the Wuskwatim Lake region in Manitoba, Canada.more » « less
-
Abstract The reduction of a large‐scale symmetric linear discrete ill‐posed problem with multiple right‐hand sides to a smaller problem with a symmetric block tridiagonal matrix can easily be carried out by the application of a small number of steps of the symmetric block Lanczos method. We show that the subdiagonal blocks of the reduced problem converge to zero fairly rapidly with increasing block number. This quick convergence indicates that there is little advantage in expressing the solutions of discrete ill‐posed problems in terms of eigenvectors of the coefficient matrix when compared with using a basis of block Lanczos vectors, which are simpler and cheaper to compute. Similarly, for nonsymmetric linear discrete ill‐posed problems with multiple right‐hand sides, we show that the solution subspace defined by a few steps of the block Golub–Kahan bidiagonalization method usually can be applied instead of the solution subspace determined by the singular value decomposition of the coefficient matrix without significant, if any, reduction of the quality of the computed solution.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1515/jiip-2019-0068
