Bidiagonalization for linear inverse problems

M. C. Jones; C. H. Travis

doi:10.1364/JOSAA.5.000660

Journal of the Optical Society of America A
Vol. 5,
Issue 5,
pp. 660-665
(1988)
•https://doi.org/10.1364/JOSAA.5.000660

Bidiagonalization for linear inverse problems

M. C. Jones and C. H. Travis

Not Accessible

Your library or personal account may give you access

Get PDF
Email
Share
Get Citation
Copy Citation Text
M. C. Jones and C. H. Travis, "Bidiagonalization for linear inverse problems," J. Opt. Soc. Am. A 5, 660-665 (1988)

Export Citation
- BibTex
- Endnote (RIS)
- HTML
- Plain Text
Citation alert
Save article

Abstract

The inversion of a linear transformation requires a stable algorithm. The algorithm should also permit regularization for noisy measurement data. The singular-value decomposition satisfies these requirements at a significant computational cost. We propose that bidiagonalization of the transformation also achieves the desired characteristics but at a much lower cost. We employ a modified Lanczos method rather than Householder transformations, as this method produces the basis vectors more directly and is more suitable for our exposition. We demonstrate the method with data previously used in the literature.

Full Article | PDF Article

More Like This

Inverse problem in optical diffusion tomography. III. Inversion formulas and singular-value decomposition

Vadim A. Markel, Vivek Mital, and John C. Schotland
J. Opt. Soc. Am. A 20(5) 890-902 (2003)

Inverse Mie problem

I. K. Ludlow and J. Everitt
J. Opt. Soc. Am. A 17(12) 2229-2235 (2000)

Inverse problem and the pseudoempirical orthogonal function method of solution. 1: Theory

Avishai Ben-David, Benjamin M. Herman, and John A. Reagan
Appl. Opt. 27(7) 1235-1242 (1988)

Previous Article Next Article

Cited By

You do not have subscription access to this journal. Cited by links are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access Optica Member Subscription

Figures (4)

You do not have subscription access to this journal. Figure files are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access Optica Member Subscription

Tables (5)

You do not have subscription access to this journal. Article tables are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access Optica Member Subscription

Equations (30)

You do not have subscription access to this journal. Equations are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access Optica Member Subscription

Algorithm Used^a	Number of Multiplications for Square Matrix
Householder tridiagonalization	5/3n³
Givens tridiagonalization	10/3n³
Standard Lanczos tridiagonalization	4n³
Modified Lanczos bidiagonalization	5n³ +n(n − 1)

i	α	β	(b_i, g)	(b_i, n)
1	7.285 × 10⁻¹	3.768 × 10⁻¹	1.830 × 10⁻¹	−9.053 × 10⁻⁴
2	6.589 × 10⁻¹	4.554 × 10⁻¹	5.253 × 10⁻¹	−1.891 × 10⁻⁴
3	2.967 × 10⁻¹	4.548 × 10⁻²	3.110 × 10⁻¹	−7.671 × 10⁻⁵
4	4.255 × 10⁻²	3.757 × 10⁻³	−6.384 × 10⁻³	−9.384 × 10⁻⁴
5	4.930 × 10⁻³	2.559 × 10⁻⁴	−2.572 × 10⁻³	3.025 × 10⁻⁴
6	3.992 × 10⁻⁴	1.206 × 10⁻⁵	−1.818 × 10⁻⁴	4.897 × 10⁻⁴
7	2.220 × 10⁻⁵	3.570 × 10⁻⁷	7.825 × 10⁻⁶	−4.565 × 10⁻⁴
8	7.939 × 10⁻⁷	5.353 × 10⁻⁹	5.952 × 10⁻⁷	−5.984 × 10⁻⁴
9	1.517 × 10⁻⁸	0	3.99 × 10⁻⁹	1.872 × 10⁻⁴
10	0	0	0	0

i	α	β	(b_i, g)	(b_i, n)
1	7.956 × 10⁻¹	3.477 × 10⁻¹	6.795 × 10⁻²	−1.458 × 10⁻³
2	5.900 × 10⁻¹	3.907 × 10⁻¹	−3.908 × 10⁻³	−1.576 × 10⁻³
3	7.319 × 10⁻¹	3.788 × 10⁻¹	−1.766 × 10⁻¹	−6.077 × 10⁻³
4	1.970 × 10⁻¹	1.925 × 10⁻¹	2.392 × 10⁻²	−2.295 × 10⁻³
5	9.690 × 10⁻¹	1.373 × 10⁻¹	6.870 × 10⁻¹	−3.213 × 10⁻³
6	3.523 × 10⁻²	3.022 × 10⁻³	7.191 × 10⁻²	−2.979 × 10⁻³
7	5.346 × 10⁻³	2.787 × 10⁻⁴	1.194 × 10⁻³	−3.361 × 10⁻³
8	6.095 × 10⁻⁴	1.766 × 10⁻⁵	4.201 × 10⁻⁴	−1.614 × 10⁻³
9	4.956 × 10⁻⁵	6.100 × 10⁻⁷	1.404 × 10⁻⁵	−1.025 × 10⁻³
10	2.516 × 10⁻⁶	0	7.394 × 10⁻⁷	−3.488 × 10⁻⁴

Algorithm	Condition	Number of Multiplications
SVD	$m ⩾ n$	3n²(m+4n)
	n > m	5m²(n+2m)
Bidiagonalization	$m ⩾ n$	$\begin{array}{l} 3 n (n + m) + 2 n^{2} m + n \\ \times \frac{(m - n)}{2} + n \frac{(n - 1)}{2} \end{array}$
	n > m	$\begin{array}{l} 3 m (n + m) + 2 n m^{2} \\ + m \frac{(m - 1)}{2} + n \frac{(n - 1)}{2} \end{array}$

Algorithm Used^a	Number of Multiplications for Square Matrix
Householder tridiagonalization	5/3n³
Givens tridiagonalization	10/3n³
Standard Lanczos tridiagonalization	4n³
Modified Lanczos bidiagonalization	5n³ +n(n − 1)

Algorithm Used	m	n	Number of Multiplications
SVD	64	10	∼31,000
Bidiagonalization	64	10	∼17,000
SVD	10	10	∼15,000
Bidiagonalization	10	10	∼2,700

Abstract

Cited By

Figures (4)

Tables (5)

Equations (30)

Journal of the Optical Society of America A