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.

© 1988 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. G. W. Steward, Introduction to Matrix Computations (Academic, New York, 1973).
  2. A. N. Tikhonov, V. Y. Arsenin, Solution of Ill-Posed Problems (Winston, Washington, D.C., 1977).
  3. A. P. Sage, J. L. Melsa, Estimation Theory with Applications to Communications and Control (McGraw-Hill, New York, 1971).
  4. See Chap. 6, Sec. 41 of Ref. 5.
  5. J. H. Wilkinson, The Algebraic Eigenvalue Problem (Oxford U. Press, Oxford, 1965).
  6. J. H. Wilkinson, “Singular Value Decomposition,” in Basic Aspects in Numerical Software—Needs and Availability. D. A. M. Jacobs, ed. (Academic, London, 1978).
  7. L. Elden, “Algorithms for the regularization of ill-conditioned least squares problem,” Bit 17, 134–145 (1977).
    [CrossRef]
  8. C. Lanczos, “An iteration method for the solution of the eigenvalue problem of linear differential and integral operators,” J. Res. Natl. Bur. Stand. 45, 255–282 (1950).
    [CrossRef]
  9. M. Bertero, C. De Mol, G. A. Viano, “On the problems of object restoration and image extrapolation in optics,” J. Math. Phys. 20, 509–521 (1979).
    [CrossRef]
  10. L. C. Sanz, T. S. Huang, “Unified Hilbert space approach to iterative least-squares linear signal restoration,” J. Opt. Soc. Am. 73, 1455–1465 (1983).
    [CrossRef]
  11. J. B. Abbis, M. Defrise, C. de Mol, H. S. Dhadwal, “Regularisation of an iterative algorithm for the extrapolation of band limited signals,” presented at the Union Radio-Scientifique International Symposium on Electromagnetic Theory, Santiago de Compostela, Spain, August 23–26, 1983.
  12. J. B. Abbis, C. de Mol, H. S. Dhadwal, “Regularised iterative and non-iterative procedures for object restoration from experimental data,” Opt. Acta 30, 107–124 (1983).
    [CrossRef]
  13. J. G. Walker, “Optical imaging with resolution exceeding the Rayleigh criterion,” Opt. Acta 30, 1197–1202 (1983).
    [CrossRef]
  14. M. C. Jones, “The discrete Gerchberg algorithm,” IEEE Trans. Acoust. Speech Signal Process. ASSP-34, 624–626 (1986).
    [CrossRef]
  15. C. K. Rushforth, A. E. Crawford, Y. Zhou, “Least-squares reconstruction of objects with missing high-frequency components,” J. Opt. Soc. Am. 72, 204–211 (1983).
    [CrossRef]
  16. F. Gori, G. Guattari, “Signal restoration for linear systems with weighted inputs. Singular value analysis for two cases of low pass filtering,” Inverse Problems 1, 67–85 (1985).
    [CrossRef]
  17. O. Sasaki, T. Yamagami, “Image restoration by iterative estimation of the expansion coefficients of an object in a singular vector space,” Opt. Lett. 10, 433–435 (1985).
    [CrossRef] [PubMed]
  18. N. Abdelmallek, N. Otsu, “Restoration of images with missing high-frequency components by minimizing the L1 norm of the solution vector,” Appl. Opt. 24, 1415–1420 (1985).
    [CrossRef]
  19. J. Maeda, “Restoration of bandlimited images by an iterative damped least-squares method with adaptive regularization,” Appl. Opt. 24, 1421–1425 (1985).
    [CrossRef] [PubMed]
  20. A. M. Darling, T. J. Hall, M. A. Fiddy, “Stable, noniterative object reconstruction from incomplete data using a priori knowledge,” J. Opt. Soc. Am. 73, 1466–1469 (1983).
    [CrossRef]
  21. M. Bertero, C. de Mol, E. R. Pike, J. G. Walker, “Resolution in diffraction limited imaging; a singular value analysis. IV. The case of uncertain localization or non-uniform illumination of the object,” Opt. Acta 31, 923–946 (1984).
    [CrossRef]
  22. NAG fortran library routine F02WCF.

1986 (1)

M. C. Jones, “The discrete Gerchberg algorithm,” IEEE Trans. Acoust. Speech Signal Process. ASSP-34, 624–626 (1986).
[CrossRef]

1985 (4)

1984 (1)

M. Bertero, C. de Mol, E. R. Pike, J. G. Walker, “Resolution in diffraction limited imaging; a singular value analysis. IV. The case of uncertain localization or non-uniform illumination of the object,” Opt. Acta 31, 923–946 (1984).
[CrossRef]

1983 (5)

1979 (1)

M. Bertero, C. De Mol, G. A. Viano, “On the problems of object restoration and image extrapolation in optics,” J. Math. Phys. 20, 509–521 (1979).
[CrossRef]

1977 (1)

L. Elden, “Algorithms for the regularization of ill-conditioned least squares problem,” Bit 17, 134–145 (1977).
[CrossRef]

1950 (1)

C. Lanczos, “An iteration method for the solution of the eigenvalue problem of linear differential and integral operators,” J. Res. Natl. Bur. Stand. 45, 255–282 (1950).
[CrossRef]

Abbis, J. B.

J. B. Abbis, C. de Mol, H. S. Dhadwal, “Regularised iterative and non-iterative procedures for object restoration from experimental data,” Opt. Acta 30, 107–124 (1983).
[CrossRef]

J. B. Abbis, M. Defrise, C. de Mol, H. S. Dhadwal, “Regularisation of an iterative algorithm for the extrapolation of band limited signals,” presented at the Union Radio-Scientifique International Symposium on Electromagnetic Theory, Santiago de Compostela, Spain, August 23–26, 1983.

Abdelmallek, N.

Arsenin, V. Y.

A. N. Tikhonov, V. Y. Arsenin, Solution of Ill-Posed Problems (Winston, Washington, D.C., 1977).

Bertero, M.

M. Bertero, C. de Mol, E. R. Pike, J. G. Walker, “Resolution in diffraction limited imaging; a singular value analysis. IV. The case of uncertain localization or non-uniform illumination of the object,” Opt. Acta 31, 923–946 (1984).
[CrossRef]

M. Bertero, C. De Mol, G. A. Viano, “On the problems of object restoration and image extrapolation in optics,” J. Math. Phys. 20, 509–521 (1979).
[CrossRef]

Crawford, A. E.

Darling, A. M.

de Mol, C.

M. Bertero, C. de Mol, E. R. Pike, J. G. Walker, “Resolution in diffraction limited imaging; a singular value analysis. IV. The case of uncertain localization or non-uniform illumination of the object,” Opt. Acta 31, 923–946 (1984).
[CrossRef]

J. B. Abbis, C. de Mol, H. S. Dhadwal, “Regularised iterative and non-iterative procedures for object restoration from experimental data,” Opt. Acta 30, 107–124 (1983).
[CrossRef]

M. Bertero, C. De Mol, G. A. Viano, “On the problems of object restoration and image extrapolation in optics,” J. Math. Phys. 20, 509–521 (1979).
[CrossRef]

J. B. Abbis, M. Defrise, C. de Mol, H. S. Dhadwal, “Regularisation of an iterative algorithm for the extrapolation of band limited signals,” presented at the Union Radio-Scientifique International Symposium on Electromagnetic Theory, Santiago de Compostela, Spain, August 23–26, 1983.

Defrise, M.

J. B. Abbis, M. Defrise, C. de Mol, H. S. Dhadwal, “Regularisation of an iterative algorithm for the extrapolation of band limited signals,” presented at the Union Radio-Scientifique International Symposium on Electromagnetic Theory, Santiago de Compostela, Spain, August 23–26, 1983.

Dhadwal, H. S.

J. B. Abbis, C. de Mol, H. S. Dhadwal, “Regularised iterative and non-iterative procedures for object restoration from experimental data,” Opt. Acta 30, 107–124 (1983).
[CrossRef]

J. B. Abbis, M. Defrise, C. de Mol, H. S. Dhadwal, “Regularisation of an iterative algorithm for the extrapolation of band limited signals,” presented at the Union Radio-Scientifique International Symposium on Electromagnetic Theory, Santiago de Compostela, Spain, August 23–26, 1983.

Elden, L.

L. Elden, “Algorithms for the regularization of ill-conditioned least squares problem,” Bit 17, 134–145 (1977).
[CrossRef]

Fiddy, M. A.

Gori, F.

F. Gori, G. Guattari, “Signal restoration for linear systems with weighted inputs. Singular value analysis for two cases of low pass filtering,” Inverse Problems 1, 67–85 (1985).
[CrossRef]

Guattari, G.

F. Gori, G. Guattari, “Signal restoration for linear systems with weighted inputs. Singular value analysis for two cases of low pass filtering,” Inverse Problems 1, 67–85 (1985).
[CrossRef]

Hall, T. J.

Huang, T. S.

Jones, M. C.

M. C. Jones, “The discrete Gerchberg algorithm,” IEEE Trans. Acoust. Speech Signal Process. ASSP-34, 624–626 (1986).
[CrossRef]

Lanczos, C.

C. Lanczos, “An iteration method for the solution of the eigenvalue problem of linear differential and integral operators,” J. Res. Natl. Bur. Stand. 45, 255–282 (1950).
[CrossRef]

Maeda, J.

Melsa, J. L.

A. P. Sage, J. L. Melsa, Estimation Theory with Applications to Communications and Control (McGraw-Hill, New York, 1971).

Otsu, N.

Pike, E. R.

M. Bertero, C. de Mol, E. R. Pike, J. G. Walker, “Resolution in diffraction limited imaging; a singular value analysis. IV. The case of uncertain localization or non-uniform illumination of the object,” Opt. Acta 31, 923–946 (1984).
[CrossRef]

Rushforth, C. K.

Sage, A. P.

A. P. Sage, J. L. Melsa, Estimation Theory with Applications to Communications and Control (McGraw-Hill, New York, 1971).

Sanz, L. C.

Sasaki, O.

Steward, G. W.

G. W. Steward, Introduction to Matrix Computations (Academic, New York, 1973).

Tikhonov, A. N.

A. N. Tikhonov, V. Y. Arsenin, Solution of Ill-Posed Problems (Winston, Washington, D.C., 1977).

Viano, G. A.

M. Bertero, C. De Mol, G. A. Viano, “On the problems of object restoration and image extrapolation in optics,” J. Math. Phys. 20, 509–521 (1979).
[CrossRef]

Walker, J. G.

M. Bertero, C. de Mol, E. R. Pike, J. G. Walker, “Resolution in diffraction limited imaging; a singular value analysis. IV. The case of uncertain localization or non-uniform illumination of the object,” Opt. Acta 31, 923–946 (1984).
[CrossRef]

J. G. Walker, “Optical imaging with resolution exceeding the Rayleigh criterion,” Opt. Acta 30, 1197–1202 (1983).
[CrossRef]

Wilkinson, J. H.

J. H. Wilkinson, The Algebraic Eigenvalue Problem (Oxford U. Press, Oxford, 1965).

J. H. Wilkinson, “Singular Value Decomposition,” in Basic Aspects in Numerical Software—Needs and Availability. D. A. M. Jacobs, ed. (Academic, London, 1978).

Yamagami, T.

Zhou, Y.

Appl. Opt. (2)

Bit (1)

L. Elden, “Algorithms for the regularization of ill-conditioned least squares problem,” Bit 17, 134–145 (1977).
[CrossRef]

IEEE Trans. Acoust. Speech Signal Process. (1)

M. C. Jones, “The discrete Gerchberg algorithm,” IEEE Trans. Acoust. Speech Signal Process. ASSP-34, 624–626 (1986).
[CrossRef]

Inverse Problems (1)

F. Gori, G. Guattari, “Signal restoration for linear systems with weighted inputs. Singular value analysis for two cases of low pass filtering,” Inverse Problems 1, 67–85 (1985).
[CrossRef]

J. Math. Phys. (1)

M. Bertero, C. De Mol, G. A. Viano, “On the problems of object restoration and image extrapolation in optics,” J. Math. Phys. 20, 509–521 (1979).
[CrossRef]

J. Opt. Soc. Am. (3)

J. Res. Natl. Bur. Stand. (1)

C. Lanczos, “An iteration method for the solution of the eigenvalue problem of linear differential and integral operators,” J. Res. Natl. Bur. Stand. 45, 255–282 (1950).
[CrossRef]

Opt. Acta (3)

M. Bertero, C. de Mol, E. R. Pike, J. G. Walker, “Resolution in diffraction limited imaging; a singular value analysis. IV. The case of uncertain localization or non-uniform illumination of the object,” Opt. Acta 31, 923–946 (1984).
[CrossRef]

J. B. Abbis, C. de Mol, H. S. Dhadwal, “Regularised iterative and non-iterative procedures for object restoration from experimental data,” Opt. Acta 30, 107–124 (1983).
[CrossRef]

J. G. Walker, “Optical imaging with resolution exceeding the Rayleigh criterion,” Opt. Acta 30, 1197–1202 (1983).
[CrossRef]

Opt. Lett. (1)

Other (8)

NAG fortran library routine F02WCF.

J. B. Abbis, M. Defrise, C. de Mol, H. S. Dhadwal, “Regularisation of an iterative algorithm for the extrapolation of band limited signals,” presented at the Union Radio-Scientifique International Symposium on Electromagnetic Theory, Santiago de Compostela, Spain, August 23–26, 1983.

G. W. Steward, Introduction to Matrix Computations (Academic, New York, 1973).

A. N. Tikhonov, V. Y. Arsenin, Solution of Ill-Posed Problems (Winston, Washington, D.C., 1977).

A. P. Sage, J. L. Melsa, Estimation Theory with Applications to Communications and Control (McGraw-Hill, New York, 1971).

See Chap. 6, Sec. 41 of Ref. 5.

J. H. Wilkinson, The Algebraic Eigenvalue Problem (Oxford U. Press, Oxford, 1965).

J. H. Wilkinson, “Singular Value Decomposition,” in Basic Aspects in Numerical Software—Needs and Availability. D. A. M. Jacobs, ed. (Academic, London, 1978).

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (4)

Fig. 1
Fig. 1

(a) The discrete signal f [Eq. (5.1)] with its band-limited (M = 9) noiseless image g. (b) and (c), the same band-limited image as in (a) corrupted with 0.1 and 4% noise, respectively.

Fig. 2
Fig. 2

The original signal and its reconstruction from the band-limited signal with 4% noise for (a) =σn2/σs2 (b) = 0.1 σn2/σs2 (c) = 0.01 σn2/σs2 for different noise samples (M = 9)

Fig. 3
Fig. 3

The same as Fig. 2 but with 0.1% noise.

Fig. 4
Fig. 4

The same as Figs. 2 and 3 with 0.001% noise for the singular, rank 9, M = 4 case.

Tables (5)

Tables Icon

Table 1 Number of Multiplications Involved in Each Algorithm for Condensation of the Matrix

Tables Icon

Table 2 Values of Parameters in Bidiagonalized Equations for M = 4

Tables Icon

Table 3 Values of Parameters in Bidiagonalized Equations for M = 9

Tables Icon

Table 4 Number of Multiplications in SVD and Bidiagonalization Algorithms

Tables Icon

Table 5 Relative Speeds of the SVD and Biadiagonalization Algorithms: a Sample Case

Equations (30)

Equations on this page are rendered with MathJax. Learn more.

g = L f + n ,
( L AB w , u ) A = ( w , L u ) B ,
L a k = γ k b k , L A B b k = γ k a k ,
( b k , g ) B = ( b k , L f ) B = ( L A B b k , f ) A = ( γ ¯ k a k , f ) A = γ k ( a k , f ) A ,
f = k γ k 1 ( b k , g ) B a k + s
f T = K γ k γ k 2 + ( b k , g ) a k ,
( L A B L + ) f = L A B g .
f ̂ LMV = f 0 + P A L A B ( R B + L P A L A B ) 1 ( g L f 0 ) ,
f ̂ LMV = f 0 + ( P A 1 + L A B R B 1 L ) 1 L A B R B 1 ( g L f 0 ) ,
( b 1 , b 1 ) B = 1 , L A B b 1 = α ¯ 1 a 1 with ( a 1 , a 1 ) A = 1 , L a 1 = α 1 b 1 + β 1 b 2 with ( b 2 , b 2 ) B = 1 , ( b 2 , b 1 ) B = 0 , L A B b 2 = β ¯ 1 a 1 + α ¯ 2 a 2 with ( a 2 , a 2 ) A = 1 , ( a 2 , a 1 ) A = 0 , L a k = α k b k + β k b k + 1 with ( b k + 1 , b k + 1 ) B = 1 , ( b k + 1 , b k ) B = 0 , L A B b k + 1 = β ¯ k a k + α ¯ k + 1 a k + 1 with ( a k + 1 , a k + 1 ) A = 1 , ( a k + 1 , a k ) A = 0 ,
[ L j k a b ] [ ( b j , L a k ) B ] = [ α 1 0 0 β 1 α 2 0 0 β 2 α 3 0 0 β 3 ]
[ L AB jk a b ] [ ( a j , L A B b k ) A ] = [ L ¯ k j b a ] = [ L j k b a ] H ,
f = k a k ( a k , f ) A ,
k L j k b a ( a k , f ) A = ( b j , g ) B .
( a 1 , f ) A = a 1 1 ( b 1 , g ) B , ( a 2 , f ) A = α 2 1 [ ( b 2 , g ) B β 1 ( a 1 , f ) B ] ,
( a 1 , a 2 ) A = ( a 1 , A a 2 ) 2
( b 1 , b 2 ) B = ( b 1 , B b 2 ) 2 ,
A = σ s 2 P 2 1 , B = σ n 2 R 2 1 ,
det ( A ) = det ( B ) = 1 ,
P A = P 2 A = σ s 2 I , R B = R 2 B = σ n 2 I .
[ | α 1 | 2 + | β 1 | 2 β ¯ 1 α 2 0 0 α ¯ 2 β 1 | α 2 | 2 + | β 2 | 2 β ¯ 2 α 3 0 0 α ¯ 3 β 2 | α 3 | 2 + | β 3 | 2 β ¯ 3 α 4 0 0 α ¯ 4 β 3 ] .
f ( n ) = { 0.5 exp [ 2 ( n 3 ) 2 ] + exp [ 2 ( n 7 ) 2 ] n = 0 , 1 , 9 0 otherwise ,
L mn = 1 64 sin ( π ( m n ) ( 2 M + 1 ) / 64 sin ( π ( m n ) / 64 ) ,
f 0 = [ 0 0 μ μ 0 0 ] , where μ = n = 0 9 f n / 10 ,
σ s 2 = n = 0 9 ( f n f 0 n ) 2 / 10 .
[ α 1 β 1 α 2 β 2 α 3 β r 1 α r ] [ ( a 1 , f ) ( a 2 , f ) . . ( a r , f ) ] = [ ( b 1 , g ) ( b 2 , g ) ( b r , g ) ] + [ ( b 1 , n ) ( b 2 , n ) ( b r , n ) ] ,
m n
m n
3 n ( n + m ) + 2 n 2 m + n × ( m n ) 2 + n ( n 1 ) 2
3 m ( n + m ) + 2 n m 2 + m ( m 1 ) 2 + n ( n 1 ) 2

Metrics