Abstract

Inversion of a finite-convolution operator is known to be an ill-posed problem. However, although the complete solution cannot be recovered to within any specified accuracy, certain components of the solution can be accurately determined. We present an estimate of the number of such components, termed here the essential dimension of the finite-convolution operator, that is dependent on the noise levels in the data, the desired accuracy in the solution, and the singular values of the finite convolution. We then show that the required singular values may be easily and accurately approximated so that the essential dimension is easily estimated and indicate its superiority over previously proposed measures of ill conditioning for this problem.

© 1985 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. A. N. Thikhonov, V. Y. Arsenin, Solutions of Ill-Posed Problems (Halsted, New York, 1977).
  2. F. Gori, F. Guattari, “Shannon number and degrees of freedom of an image.” Opt. Commun. 7, 163–165 (1973).
    [CrossRef]
  3. M. Bendinelli, A. Consortini, L. Ronchi, B. Roy Frieden, “Degrees of freedom and eigenfunctions for the noisy image,” J. Opt. Soc. Am. 64, 1498–1502 (1974).
    [CrossRef]
  4. G. N. Newsam, “Filtered inversion of partially known transforms” Ph.D. dissertation (Harvard University, Cambridge, Mass., 1982).
  5. R. Barakat, G. Newsam, “Algorithms for reconstruction of partially known, bandlimited Fourier transform pairs from noisy data: I. The prototypical linear problem.” J. Integral Eq. Suppl. 9, 49–76 (1985).
  6. R. Barakat, G. Newsam, “Algorithms for reconstruction of partially known, bandlimited Fourier transform pairs from noisy data: II. The nonlinear problem of phase retrieval.” J. Integral Eq. Suppl. 9, 77–125 (1985).
  7. G. Toraldo di Francia, “Resolving power and information,” J. Opt. Soc. Am. 45, 497–500 (1955).
    [CrossRef]
  8. G. Toraldo di Francia, “Directivity, super-gain, and information,” IRE Trans. Antennas Propag. AP-4, 473–478 (1956).
    [CrossRef]
  9. D. Slepian, H. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty—I,” Bell Syst. Tech. J. 40, 43–64 (1961).
    [CrossRef]
  10. H. Landau, H. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty—II,” Bell Syst. Tech. J. 40, 65–84 (1961).
    [CrossRef]
  11. H. Landau, H. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty—III,” Bell Syst. Tech. J. 41, 1295–1326 (1962).
    [CrossRef]
  12. D. Slepian, “Prolate spheroidal wave functions, Fourier analysis and uncertainty—IV,” Bell Syst. Tech. J. 44, 4009–4057 (1964).
  13. D. Slepian, “Some asymptotic expansions of prolate spheroidal wave functions,” J. Math Phys. (Cambridge, Mass.) 44, 99–140 (1965).
  14. H. Landau, “The eigenvalue behavior of certain convolution equations,” Trans. Am. Math. Soc. 115, 566–569 (1964).
  15. H. Landau, H. Widom, “Eigenvalue distribution of time and frequency limiting,” J. Math. Anal. Appl. 77, 469–481 (1980).
    [CrossRef]
  16. F. Gori, C. Palma, “On the eigenvalues of the sinc2 kernel,” J. Phys. A 11, 1709–1719 (1975).
    [CrossRef]
  17. R. Barakat, “Shannon numbers of diffraction images,” Opt. Commun. 42, 391–394 (1982).
    [CrossRef]
  18. C. T. H. Baker, The Numerical Treatment of Integral Equations (Clarendon, Oxford, 1977).
  19. J. A. Cochran, The Analysis of Linear Integral Equations (McGraw-Hill, New York, 1972).
  20. U. Grenander, G. Szego, Toeplitz Forms and Their Applications (U. California Press, Los Angeles, Calif., 1958).
  21. H. Widom, “Asymptotic behavior of the eigenvalues of certain integral equations, II.” Arch. Rational Mech. Anal. 17, 215–229 (1964).
    [CrossRef]
  22. R. Boas, Entire Function (Academic, New York, 1954).

1985 (2)

R. Barakat, G. Newsam, “Algorithms for reconstruction of partially known, bandlimited Fourier transform pairs from noisy data: I. The prototypical linear problem.” J. Integral Eq. Suppl. 9, 49–76 (1985).

R. Barakat, G. Newsam, “Algorithms for reconstruction of partially known, bandlimited Fourier transform pairs from noisy data: II. The nonlinear problem of phase retrieval.” J. Integral Eq. Suppl. 9, 77–125 (1985).

1982 (1)

R. Barakat, “Shannon numbers of diffraction images,” Opt. Commun. 42, 391–394 (1982).
[CrossRef]

1980 (1)

H. Landau, H. Widom, “Eigenvalue distribution of time and frequency limiting,” J. Math. Anal. Appl. 77, 469–481 (1980).
[CrossRef]

1975 (1)

F. Gori, C. Palma, “On the eigenvalues of the sinc2 kernel,” J. Phys. A 11, 1709–1719 (1975).
[CrossRef]

1974 (1)

1973 (1)

F. Gori, F. Guattari, “Shannon number and degrees of freedom of an image.” Opt. Commun. 7, 163–165 (1973).
[CrossRef]

1965 (1)

D. Slepian, “Some asymptotic expansions of prolate spheroidal wave functions,” J. Math Phys. (Cambridge, Mass.) 44, 99–140 (1965).

1964 (3)

H. Landau, “The eigenvalue behavior of certain convolution equations,” Trans. Am. Math. Soc. 115, 566–569 (1964).

D. Slepian, “Prolate spheroidal wave functions, Fourier analysis and uncertainty—IV,” Bell Syst. Tech. J. 44, 4009–4057 (1964).

H. Widom, “Asymptotic behavior of the eigenvalues of certain integral equations, II.” Arch. Rational Mech. Anal. 17, 215–229 (1964).
[CrossRef]

1962 (1)

H. Landau, H. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty—III,” Bell Syst. Tech. J. 41, 1295–1326 (1962).
[CrossRef]

1961 (2)

D. Slepian, H. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty—I,” Bell Syst. Tech. J. 40, 43–64 (1961).
[CrossRef]

H. Landau, H. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty—II,” Bell Syst. Tech. J. 40, 65–84 (1961).
[CrossRef]

1956 (1)

G. Toraldo di Francia, “Directivity, super-gain, and information,” IRE Trans. Antennas Propag. AP-4, 473–478 (1956).
[CrossRef]

1955 (1)

Arsenin, V. Y.

A. N. Thikhonov, V. Y. Arsenin, Solutions of Ill-Posed Problems (Halsted, New York, 1977).

Baker, C. T. H.

C. T. H. Baker, The Numerical Treatment of Integral Equations (Clarendon, Oxford, 1977).

Barakat, R.

R. Barakat, G. Newsam, “Algorithms for reconstruction of partially known, bandlimited Fourier transform pairs from noisy data: I. The prototypical linear problem.” J. Integral Eq. Suppl. 9, 49–76 (1985).

R. Barakat, G. Newsam, “Algorithms for reconstruction of partially known, bandlimited Fourier transform pairs from noisy data: II. The nonlinear problem of phase retrieval.” J. Integral Eq. Suppl. 9, 77–125 (1985).

R. Barakat, “Shannon numbers of diffraction images,” Opt. Commun. 42, 391–394 (1982).
[CrossRef]

Bendinelli, M.

Boas, R.

R. Boas, Entire Function (Academic, New York, 1954).

Cochran, J. A.

J. A. Cochran, The Analysis of Linear Integral Equations (McGraw-Hill, New York, 1972).

Consortini, A.

Gori, F.

F. Gori, C. Palma, “On the eigenvalues of the sinc2 kernel,” J. Phys. A 11, 1709–1719 (1975).
[CrossRef]

F. Gori, F. Guattari, “Shannon number and degrees of freedom of an image.” Opt. Commun. 7, 163–165 (1973).
[CrossRef]

Grenander, U.

U. Grenander, G. Szego, Toeplitz Forms and Their Applications (U. California Press, Los Angeles, Calif., 1958).

Guattari, F.

F. Gori, F. Guattari, “Shannon number and degrees of freedom of an image.” Opt. Commun. 7, 163–165 (1973).
[CrossRef]

Landau, H.

H. Landau, H. Widom, “Eigenvalue distribution of time and frequency limiting,” J. Math. Anal. Appl. 77, 469–481 (1980).
[CrossRef]

H. Landau, “The eigenvalue behavior of certain convolution equations,” Trans. Am. Math. Soc. 115, 566–569 (1964).

H. Landau, H. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty—III,” Bell Syst. Tech. J. 41, 1295–1326 (1962).
[CrossRef]

H. Landau, H. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty—II,” Bell Syst. Tech. J. 40, 65–84 (1961).
[CrossRef]

Newsam, G.

R. Barakat, G. Newsam, “Algorithms for reconstruction of partially known, bandlimited Fourier transform pairs from noisy data: II. The nonlinear problem of phase retrieval.” J. Integral Eq. Suppl. 9, 77–125 (1985).

R. Barakat, G. Newsam, “Algorithms for reconstruction of partially known, bandlimited Fourier transform pairs from noisy data: I. The prototypical linear problem.” J. Integral Eq. Suppl. 9, 49–76 (1985).

Newsam, G. N.

G. N. Newsam, “Filtered inversion of partially known transforms” Ph.D. dissertation (Harvard University, Cambridge, Mass., 1982).

Palma, C.

F. Gori, C. Palma, “On the eigenvalues of the sinc2 kernel,” J. Phys. A 11, 1709–1719 (1975).
[CrossRef]

Pollak, H.

H. Landau, H. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty—III,” Bell Syst. Tech. J. 41, 1295–1326 (1962).
[CrossRef]

D. Slepian, H. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty—I,” Bell Syst. Tech. J. 40, 43–64 (1961).
[CrossRef]

H. Landau, H. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty—II,” Bell Syst. Tech. J. 40, 65–84 (1961).
[CrossRef]

Ronchi, L.

Roy Frieden, B.

Slepian, D.

D. Slepian, “Some asymptotic expansions of prolate spheroidal wave functions,” J. Math Phys. (Cambridge, Mass.) 44, 99–140 (1965).

D. Slepian, “Prolate spheroidal wave functions, Fourier analysis and uncertainty—IV,” Bell Syst. Tech. J. 44, 4009–4057 (1964).

D. Slepian, H. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty—I,” Bell Syst. Tech. J. 40, 43–64 (1961).
[CrossRef]

Szego, G.

U. Grenander, G. Szego, Toeplitz Forms and Their Applications (U. California Press, Los Angeles, Calif., 1958).

Thikhonov, A. N.

A. N. Thikhonov, V. Y. Arsenin, Solutions of Ill-Posed Problems (Halsted, New York, 1977).

Toraldo di Francia, G.

G. Toraldo di Francia, “Directivity, super-gain, and information,” IRE Trans. Antennas Propag. AP-4, 473–478 (1956).
[CrossRef]

G. Toraldo di Francia, “Resolving power and information,” J. Opt. Soc. Am. 45, 497–500 (1955).
[CrossRef]

Widom, H.

H. Landau, H. Widom, “Eigenvalue distribution of time and frequency limiting,” J. Math. Anal. Appl. 77, 469–481 (1980).
[CrossRef]

H. Widom, “Asymptotic behavior of the eigenvalues of certain integral equations, II.” Arch. Rational Mech. Anal. 17, 215–229 (1964).
[CrossRef]

Arch. Rational Mech. Anal. (1)

H. Widom, “Asymptotic behavior of the eigenvalues of certain integral equations, II.” Arch. Rational Mech. Anal. 17, 215–229 (1964).
[CrossRef]

Bell Syst. Tech. J. (4)

D. Slepian, H. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty—I,” Bell Syst. Tech. J. 40, 43–64 (1961).
[CrossRef]

H. Landau, H. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty—II,” Bell Syst. Tech. J. 40, 65–84 (1961).
[CrossRef]

H. Landau, H. Pollak, “Prolate spheroidal wave functions, Fourier analysis and uncertainty—III,” Bell Syst. Tech. J. 41, 1295–1326 (1962).
[CrossRef]

D. Slepian, “Prolate spheroidal wave functions, Fourier analysis and uncertainty—IV,” Bell Syst. Tech. J. 44, 4009–4057 (1964).

IRE Trans. Antennas Propag. (1)

G. Toraldo di Francia, “Directivity, super-gain, and information,” IRE Trans. Antennas Propag. AP-4, 473–478 (1956).
[CrossRef]

J. Integral Eq. Suppl. (2)

R. Barakat, G. Newsam, “Algorithms for reconstruction of partially known, bandlimited Fourier transform pairs from noisy data: I. The prototypical linear problem.” J. Integral Eq. Suppl. 9, 49–76 (1985).

R. Barakat, G. Newsam, “Algorithms for reconstruction of partially known, bandlimited Fourier transform pairs from noisy data: II. The nonlinear problem of phase retrieval.” J. Integral Eq. Suppl. 9, 77–125 (1985).

J. Math Phys. (Cambridge, Mass.) (1)

D. Slepian, “Some asymptotic expansions of prolate spheroidal wave functions,” J. Math Phys. (Cambridge, Mass.) 44, 99–140 (1965).

J. Math. Anal. Appl. (1)

H. Landau, H. Widom, “Eigenvalue distribution of time and frequency limiting,” J. Math. Anal. Appl. 77, 469–481 (1980).
[CrossRef]

J. Opt. Soc. Am. (2)

J. Phys. A (1)

F. Gori, C. Palma, “On the eigenvalues of the sinc2 kernel,” J. Phys. A 11, 1709–1719 (1975).
[CrossRef]

Opt. Commun. (2)

R. Barakat, “Shannon numbers of diffraction images,” Opt. Commun. 42, 391–394 (1982).
[CrossRef]

F. Gori, F. Guattari, “Shannon number and degrees of freedom of an image.” Opt. Commun. 7, 163–165 (1973).
[CrossRef]

Trans. Am. Math. Soc. (1)

H. Landau, “The eigenvalue behavior of certain convolution equations,” Trans. Am. Math. Soc. 115, 566–569 (1964).

Other (6)

C. T. H. Baker, The Numerical Treatment of Integral Equations (Clarendon, Oxford, 1977).

J. A. Cochran, The Analysis of Linear Integral Equations (McGraw-Hill, New York, 1972).

U. Grenander, G. Szego, Toeplitz Forms and Their Applications (U. California Press, Los Angeles, Calif., 1958).

A. N. Thikhonov, V. Y. Arsenin, Solutions of Ill-Posed Problems (Halsted, New York, 1977).

R. Boas, Entire Function (Academic, New York, 1954).

G. N. Newsam, “Filtered inversion of partially known transforms” Ph.D. dissertation (Harvard University, Cambridge, Mass., 1982).

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 (5)

Fig. 1
Fig. 1

Distribution of singular values σn for the (sinc) kernel k1(t), Eq. (4.1). Since the kernel is symmetric, this is also the distribution of eigenvalues λn.

Fig. 2
Fig. 2

Distribution of singular values σn for the (sinc)2 kernel k2(t), Eq. (4.2). Since the kernel is symmetric, this is also the distribution of eigenvalues λn.

Fig. 3
Fig. 3

Distribution of singular values σn for k3(t), Eq. (4.3).

Fig. 4
Fig. 4

Distribution of singular values σn for k4(t), Eq. (4.4).

Fig. 5
Fig. 5

Distribution of singular values σn for the composite kernel k5(t), Eq. (4.5).

Tables (1)

Tables Icon

Table 1 Essential Dimension and Shannon Numbers S of K j

Equations (51)

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

g ( s ) = 1 1 k [ c ( s t ) ] f ( t ) d t
( K f ) ( s ) 1 1 k [ c ( s t ) ] f ( t ) d t .
k ( c t ) = sin c 2 π t π t 2 c sin c ( c π t ) ,
n ( c , α ) = 4 c + 2 π 2 log ( α 1 1 ) log c + o ( log c ) .
n = 4 c + 2 b π 2 log [ 2 ( 2 π c ) 1 / 2 ] ,
lim n λ n = ( 1 + e b ) 1 .
λ n ~ 1 if n < 4 c ~ 0 if n > 4 c ,
S ( K ) n = 1 λ n = tr ( K )
S ( K ) = 1 + 1 k ( s s ) d s = 2 k ( 0 ) ,
k ( t ) = 2 c sinc 2 ( c 2 π t ) ,
S ( K ) = 2 K ( 0 ) = 4 c .
K ϕ n = σ n ψ n .
g = n b n ψ n ,
f = n b n σ n 1 ϕ n n a n ϕ n .
K h = g , K h = g
σ N 1 + 1 < ( / δ ) σ N 1 .
( / δ ) > 1 N ( δ , ) = 0 for g , ( / δ ) < 1 N ( δ , ) N 1 for g ,
σ N 1 + 1 < σ 1 ( / δ ) σ N 1
( c f ) ( r ) = 1 1 exp ( 2 π irt ) f ( t ) d t , r [ c , c ] .
( f ) ( r ) = exp ( 2 π irt ) f ( t ) d t .
P c f ) ( t ) = f ( t ) if t c I = 0 otherwise .
μ K f ( r ) K ( r ) f ( r ) .
| k ( t ) | d t < .
K : L 2 ( I ) L 2 ( I ) is a bounded linear operator , K = P * μ K P , K max r | K ( r ) .
σ n ( K 1 σ n ( K 2 ) n .
σ n ( K 1 + K 2 σ n ( K 1 ) + K 2 .
σ n ( K ) min c { | K ( c ) | + [ | K ( o ) | | K ( c ) | ] σ n ( c ) } .
K f μ K P f f L 2 ( I ) = [ | K 2 ( r ) | ( f ) ( r ) | 2 d r ] 1 / 2 = μ | K | P f ,
K 1 ( r ) = | K ( c ) | if r c I = | K ( r ) | if r c I ,
K 2 ( r ) = | K ( r ) | | K ( c ) | if r c I = 0 if r c I .
1 μ K ( 1 ) = max r K 1 ( r ) = | K ( c ) | ,
σ ( 2 ( | K ( o ) | K ( c ) | ) σ ( P c P ) .
σ n ( K ) max c [ K ( c ) σ n 2 ( c ) ] .
K 1 ( r ) = K ( c ) if r c I = 0 if r c I ;
P * μ K ( 1 ) P = K ( c ) c * c
σ n ( K ) K ( c ) σ n 2 ( c ) .
n = 4 c 8 π 2 log ( | K ( c ) | ) log [ 2 ( 2 π c ) 1 / 2 ]
σ n ( K ) | K ( c ) | + [ | K ( o ) | | K ( c ) | ] σ n ( c ) ~ | K ( c ) | + [ | K ( o ) | | K ( c ) | ] [ 1 + | K ( c ) | 4 ] 1 / 2 ~ | K ( c ) | + | K ( o ) | | K ( c ) | 2 ~ | K ( c ) | .
n ~ 4 c + 8 β π 2 log ( α c ) , log [ 2 ( 2 π c ) 1 / 2 ] 4 c + P ( c ) ,
| K ( c ) | ~ α | c | β ~ α ( n 4 ) β [ 1 P ( c ) n ] β ~ α n β 4 ~ | K ( n 4 ) | ,
k 1 ( t ) = sin 8 π t π t ,
k 2 ( t ) = sin 2 4 π t 2 π 2 t 2
k 3 ( t ) = sin 2 2 π t 2 π 2 t 2 ,
k 4 ( t ) = 4 π 1 / 2 exp ( 16 t 2 ) ,
k 5 ( t ) = 1 3 k 1 ( t ) + 2 3 k 2 ( t ) .
K 1 ( r ) = 1 , r 4 I ,
K 2 ( r ) = 1 | r | / 4 , r 4 I ,
K 3 ( r ) = 1 | r | / 2 , r 2 I ,
K 4 ( r ) = exp ( π 2 r 2 / 16 ) ,
K 5 ( r ) = 1 3 [ K 1 ( r ) + 2 K 2 ( r ) ] .
S ( K j )

Metrics