Abstract

In many applications, sampled data are collected in irregular fashion or are partly lost or unavailable. In these cases, it is necessary to convert irregularly sampled signals to regularly sampled ones or to restore missing data. We address this problem in the framework of a discrete sampling theorem for band-limited discrete signals that have a limited number of nonzero transform coefficients in a certain transform domain. Conditions for the image unique recovery, from sparse samples, are formulated and then analyzed for various transforms. Applications are demonstrated on examples of image superresolution and image reconstruction from sparse projections.

© 2009 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. D. Shepard, “A two-dimensional interpolation function for irregularly-spaced data,” in Proceedings of the 1968 ACM 23rd National Conference (ACM, 1968), pp. 517-523.
    [CrossRef]
  2. S. K. Lodha and R. Franke, “Scattered data techniques for surfaces,” in Proceedings of the IEEE Conference on Scientific Visualization (IEEE, 1997), Vol. 38, No. 157, pp. 181-200.
  3. H. Landau, “Necessary density conditions for sampling and interpolation of certain entire functions,” Acta Math. 117, 37-52 (1967).
    [CrossRef]
  4. A. Aldroubi and K. Grochenig, “Non-uniform sampling and reconstruction in shift-invariant spaces,” SIAM Rev. 43, 585-620 (2001).
    [CrossRef]
  5. F.Marvasti, ed., Nonuniform Sampling (Kluwer Academic/Plenum, 2001).
    [CrossRef]
  6. M. Unser, “Splines: a perfect fit for signal and image processing,” IEEE Signal Process. Mag. June 1999, pp. 22-38.
    [CrossRef]
  7. S. Lee, G. Wolberg, and S. Y. Shin, “Scattered data interpolation with multilevel B-splines,” IEEE Trans. Visualization. Comput. Graphics 3, 228-244 (1997).
    [CrossRef]
  8. E. Margolis and Y. C. Eldar, “Interpolation with non-uniform B-splines,” in Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (IEEE, 2004), Vol. 2, pp. 577-580.
  9. P. J. S. G. Ferreira, “Iterative and noniterative recovery of missing samples for 1-D band-limited signals,” in Nonuniform Sampling, F.Marvasti, ed. (Kluwer Academic/Plenum, 2001), pp. 235-278.
    [CrossRef]
  10. M. Hasan and F. Marvasti, “Application of nonuniform sampling to error concealment,” in Nonuniform Sampling, F.Marvasti, ed. (Kluwer Academic/Plenum, 2001), pp. 619-646.
  11. A. Averbuch, R. Coifman, M. Israeli, I. Sidelnikov, and Y. Shkolinsky, “Irregular sampling for multi-dimensional polar processing of integral transforms,” in Advances in Signal Transforms: Theory and Applications, J.Astola and L.Yaroslavsky, eds. (Hindawi, 2007), pp. 143-198.
  12. A. Averbuch and V. Zheludev, “Wavelet and frame transforms originated from continuous and discrete splines,” in Advances in Signal Transforms: Theory and Applications, J.Astola and L.Yaroslavsky, eds. (Hindawi, 2007), pp. 1-54.
  13. Compressed sensing resources: http://www.dsp.ece.rice.edu/cs/. Last accessed December 18, 2008.
  14. Y. Katiyi and L. Yaroslavsky, “Regular matrix methods for synthesis of fast transforms: general pruned and integer-to-integer transforms,” in Proceedings of IEEE International Workshop on Spectral Methods and Multirate Signal Processing (IEEE, 2001), pp. 17-24.
  15. Y. Katiyi and L. Yaroslavsky, “V/HS structure for transforms and their fast algorithms,” in Proceedings of the IEEE 3rd International Symposium on Signal Processing and Analysis (IEEE, 2003), Vol. 1, pp. 482--487.
  16. L. Yaroslavsky, Digital Holography and Digital Signal Processing (Kluwer Academic, 2004).
  17. A. Papoulis, “A new algorithm in spectral analysis and band-limited extrapolation,” IEEE Trans. Circuits Syst. 22, pp. 735-742 (1975).
    [CrossRef]
  18. R. A. Horn and C. R. Johnson, Topics in Matrix Analysis (Cambridge U. Press, 1991).
    [CrossRef]
  19. L. Yaroslavsky, “Fast discrete sinc-interpolation: a gold standard for image resampling,” in Advances in Signal Transforms: Theory and Application, J.Astola and L.Yaroslavsky, eds., EURASIP Book Series on Signal Processing and Communications (Hindawi, 2007), pp. 337-405.
  20. L. P. Yaroslavsky, B. Fishbain, G. Shabat, and I. Ideses, “Super-resolution in turbulent videos: making profit from damage,” Opt. Lett. 32, 3038-3040 (2007).
    [CrossRef] [PubMed]
  21. A. Averbuch, R. Coifman, D. Donoho, M. Israeli, and Y. Shkolinsky, “A framework for discrete integral transformations II--the 2D discrete Radon transform,” SIAM J. Sci. Comput. (USA) 30, 764-784 (2008).
    [CrossRef]
  22. Standford University, Statistics Department, David Donoho's homepage,http://www.stat.stanford.edu/~donoho/.

2008 (1)

A. Averbuch, R. Coifman, D. Donoho, M. Israeli, and Y. Shkolinsky, “A framework for discrete integral transformations II--the 2D discrete Radon transform,” SIAM J. Sci. Comput. (USA) 30, 764-784 (2008).
[CrossRef]

2007 (1)

2001 (1)

A. Aldroubi and K. Grochenig, “Non-uniform sampling and reconstruction in shift-invariant spaces,” SIAM Rev. 43, 585-620 (2001).
[CrossRef]

1999 (1)

M. Unser, “Splines: a perfect fit for signal and image processing,” IEEE Signal Process. Mag. June 1999, pp. 22-38.
[CrossRef]

1997 (1)

S. Lee, G. Wolberg, and S. Y. Shin, “Scattered data interpolation with multilevel B-splines,” IEEE Trans. Visualization. Comput. Graphics 3, 228-244 (1997).
[CrossRef]

1975 (1)

A. Papoulis, “A new algorithm in spectral analysis and band-limited extrapolation,” IEEE Trans. Circuits Syst. 22, pp. 735-742 (1975).
[CrossRef]

1967 (1)

H. Landau, “Necessary density conditions for sampling and interpolation of certain entire functions,” Acta Math. 117, 37-52 (1967).
[CrossRef]

Aldroubi, A.

A. Aldroubi and K. Grochenig, “Non-uniform sampling and reconstruction in shift-invariant spaces,” SIAM Rev. 43, 585-620 (2001).
[CrossRef]

Averbuch, A.

A. Averbuch, R. Coifman, D. Donoho, M. Israeli, and Y. Shkolinsky, “A framework for discrete integral transformations II--the 2D discrete Radon transform,” SIAM J. Sci. Comput. (USA) 30, 764-784 (2008).
[CrossRef]

A. Averbuch, R. Coifman, M. Israeli, I. Sidelnikov, and Y. Shkolinsky, “Irregular sampling for multi-dimensional polar processing of integral transforms,” in Advances in Signal Transforms: Theory and Applications, J.Astola and L.Yaroslavsky, eds. (Hindawi, 2007), pp. 143-198.

A. Averbuch and V. Zheludev, “Wavelet and frame transforms originated from continuous and discrete splines,” in Advances in Signal Transforms: Theory and Applications, J.Astola and L.Yaroslavsky, eds. (Hindawi, 2007), pp. 1-54.

Coifman, R.

A. Averbuch, R. Coifman, D. Donoho, M. Israeli, and Y. Shkolinsky, “A framework for discrete integral transformations II--the 2D discrete Radon transform,” SIAM J. Sci. Comput. (USA) 30, 764-784 (2008).
[CrossRef]

A. Averbuch, R. Coifman, M. Israeli, I. Sidelnikov, and Y. Shkolinsky, “Irregular sampling for multi-dimensional polar processing of integral transforms,” in Advances in Signal Transforms: Theory and Applications, J.Astola and L.Yaroslavsky, eds. (Hindawi, 2007), pp. 143-198.

Donoho, D.

A. Averbuch, R. Coifman, D. Donoho, M. Israeli, and Y. Shkolinsky, “A framework for discrete integral transformations II--the 2D discrete Radon transform,” SIAM J. Sci. Comput. (USA) 30, 764-784 (2008).
[CrossRef]

Eldar, Y. C.

E. Margolis and Y. C. Eldar, “Interpolation with non-uniform B-splines,” in Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (IEEE, 2004), Vol. 2, pp. 577-580.

Ferreira, P. J. S. G.

P. J. S. G. Ferreira, “Iterative and noniterative recovery of missing samples for 1-D band-limited signals,” in Nonuniform Sampling, F.Marvasti, ed. (Kluwer Academic/Plenum, 2001), pp. 235-278.
[CrossRef]

Fishbain, B.

Franke, R.

S. K. Lodha and R. Franke, “Scattered data techniques for surfaces,” in Proceedings of the IEEE Conference on Scientific Visualization (IEEE, 1997), Vol. 38, No. 157, pp. 181-200.

Grochenig, K.

A. Aldroubi and K. Grochenig, “Non-uniform sampling and reconstruction in shift-invariant spaces,” SIAM Rev. 43, 585-620 (2001).
[CrossRef]

Hasan, M.

M. Hasan and F. Marvasti, “Application of nonuniform sampling to error concealment,” in Nonuniform Sampling, F.Marvasti, ed. (Kluwer Academic/Plenum, 2001), pp. 619-646.

Horn, R. A.

R. A. Horn and C. R. Johnson, Topics in Matrix Analysis (Cambridge U. Press, 1991).
[CrossRef]

Ideses, I.

Israeli, M.

A. Averbuch, R. Coifman, D. Donoho, M. Israeli, and Y. Shkolinsky, “A framework for discrete integral transformations II--the 2D discrete Radon transform,” SIAM J. Sci. Comput. (USA) 30, 764-784 (2008).
[CrossRef]

A. Averbuch, R. Coifman, M. Israeli, I. Sidelnikov, and Y. Shkolinsky, “Irregular sampling for multi-dimensional polar processing of integral transforms,” in Advances in Signal Transforms: Theory and Applications, J.Astola and L.Yaroslavsky, eds. (Hindawi, 2007), pp. 143-198.

Johnson, C. R.

R. A. Horn and C. R. Johnson, Topics in Matrix Analysis (Cambridge U. Press, 1991).
[CrossRef]

Katiyi, Y.

Y. Katiyi and L. Yaroslavsky, “Regular matrix methods for synthesis of fast transforms: general pruned and integer-to-integer transforms,” in Proceedings of IEEE International Workshop on Spectral Methods and Multirate Signal Processing (IEEE, 2001), pp. 17-24.

Y. Katiyi and L. Yaroslavsky, “V/HS structure for transforms and their fast algorithms,” in Proceedings of the IEEE 3rd International Symposium on Signal Processing and Analysis (IEEE, 2003), Vol. 1, pp. 482--487.

Landau, H.

H. Landau, “Necessary density conditions for sampling and interpolation of certain entire functions,” Acta Math. 117, 37-52 (1967).
[CrossRef]

Lee, S.

S. Lee, G. Wolberg, and S. Y. Shin, “Scattered data interpolation with multilevel B-splines,” IEEE Trans. Visualization. Comput. Graphics 3, 228-244 (1997).
[CrossRef]

Lodha, S. K.

S. K. Lodha and R. Franke, “Scattered data techniques for surfaces,” in Proceedings of the IEEE Conference on Scientific Visualization (IEEE, 1997), Vol. 38, No. 157, pp. 181-200.

Margolis, E.

E. Margolis and Y. C. Eldar, “Interpolation with non-uniform B-splines,” in Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (IEEE, 2004), Vol. 2, pp. 577-580.

Marvasti, F.

M. Hasan and F. Marvasti, “Application of nonuniform sampling to error concealment,” in Nonuniform Sampling, F.Marvasti, ed. (Kluwer Academic/Plenum, 2001), pp. 619-646.

Papoulis, A.

A. Papoulis, “A new algorithm in spectral analysis and band-limited extrapolation,” IEEE Trans. Circuits Syst. 22, pp. 735-742 (1975).
[CrossRef]

Shabat, G.

Shepard, D.

D. Shepard, “A two-dimensional interpolation function for irregularly-spaced data,” in Proceedings of the 1968 ACM 23rd National Conference (ACM, 1968), pp. 517-523.
[CrossRef]

Shin, S. Y.

S. Lee, G. Wolberg, and S. Y. Shin, “Scattered data interpolation with multilevel B-splines,” IEEE Trans. Visualization. Comput. Graphics 3, 228-244 (1997).
[CrossRef]

Shkolinsky, Y.

A. Averbuch, R. Coifman, D. Donoho, M. Israeli, and Y. Shkolinsky, “A framework for discrete integral transformations II--the 2D discrete Radon transform,” SIAM J. Sci. Comput. (USA) 30, 764-784 (2008).
[CrossRef]

A. Averbuch, R. Coifman, M. Israeli, I. Sidelnikov, and Y. Shkolinsky, “Irregular sampling for multi-dimensional polar processing of integral transforms,” in Advances in Signal Transforms: Theory and Applications, J.Astola and L.Yaroslavsky, eds. (Hindawi, 2007), pp. 143-198.

Sidelnikov, I.

A. Averbuch, R. Coifman, M. Israeli, I. Sidelnikov, and Y. Shkolinsky, “Irregular sampling for multi-dimensional polar processing of integral transforms,” in Advances in Signal Transforms: Theory and Applications, J.Astola and L.Yaroslavsky, eds. (Hindawi, 2007), pp. 143-198.

Unser, M.

M. Unser, “Splines: a perfect fit for signal and image processing,” IEEE Signal Process. Mag. June 1999, pp. 22-38.
[CrossRef]

Wolberg, G.

S. Lee, G. Wolberg, and S. Y. Shin, “Scattered data interpolation with multilevel B-splines,” IEEE Trans. Visualization. Comput. Graphics 3, 228-244 (1997).
[CrossRef]

Yaroslavsky, L.

Y. Katiyi and L. Yaroslavsky, “Regular matrix methods for synthesis of fast transforms: general pruned and integer-to-integer transforms,” in Proceedings of IEEE International Workshop on Spectral Methods and Multirate Signal Processing (IEEE, 2001), pp. 17-24.

L. Yaroslavsky, Digital Holography and Digital Signal Processing (Kluwer Academic, 2004).

Y. Katiyi and L. Yaroslavsky, “V/HS structure for transforms and their fast algorithms,” in Proceedings of the IEEE 3rd International Symposium on Signal Processing and Analysis (IEEE, 2003), Vol. 1, pp. 482--487.

L. Yaroslavsky, “Fast discrete sinc-interpolation: a gold standard for image resampling,” in Advances in Signal Transforms: Theory and Application, J.Astola and L.Yaroslavsky, eds., EURASIP Book Series on Signal Processing and Communications (Hindawi, 2007), pp. 337-405.

Yaroslavsky, L. P.

Zheludev, V.

A. Averbuch and V. Zheludev, “Wavelet and frame transforms originated from continuous and discrete splines,” in Advances in Signal Transforms: Theory and Applications, J.Astola and L.Yaroslavsky, eds. (Hindawi, 2007), pp. 1-54.

Acta Math. (1)

H. Landau, “Necessary density conditions for sampling and interpolation of certain entire functions,” Acta Math. 117, 37-52 (1967).
[CrossRef]

IEEE Signal Process. Mag. (1)

M. Unser, “Splines: a perfect fit for signal and image processing,” IEEE Signal Process. Mag. June 1999, pp. 22-38.
[CrossRef]

IEEE Trans. Circuits Syst. (1)

A. Papoulis, “A new algorithm in spectral analysis and band-limited extrapolation,” IEEE Trans. Circuits Syst. 22, pp. 735-742 (1975).
[CrossRef]

IEEE Trans. Visualization. Comput. Graphics (1)

S. Lee, G. Wolberg, and S. Y. Shin, “Scattered data interpolation with multilevel B-splines,” IEEE Trans. Visualization. Comput. Graphics 3, 228-244 (1997).
[CrossRef]

Opt. Lett. (1)

SIAM J. Sci. Comput. (USA) (1)

A. Averbuch, R. Coifman, D. Donoho, M. Israeli, and Y. Shkolinsky, “A framework for discrete integral transformations II--the 2D discrete Radon transform,” SIAM J. Sci. Comput. (USA) 30, 764-784 (2008).
[CrossRef]

SIAM Rev. (1)

A. Aldroubi and K. Grochenig, “Non-uniform sampling and reconstruction in shift-invariant spaces,” SIAM Rev. 43, 585-620 (2001).
[CrossRef]

Other (15)

F.Marvasti, ed., Nonuniform Sampling (Kluwer Academic/Plenum, 2001).
[CrossRef]

D. Shepard, “A two-dimensional interpolation function for irregularly-spaced data,” in Proceedings of the 1968 ACM 23rd National Conference (ACM, 1968), pp. 517-523.
[CrossRef]

S. K. Lodha and R. Franke, “Scattered data techniques for surfaces,” in Proceedings of the IEEE Conference on Scientific Visualization (IEEE, 1997), Vol. 38, No. 157, pp. 181-200.

Standford University, Statistics Department, David Donoho's homepage,http://www.stat.stanford.edu/~donoho/.

R. A. Horn and C. R. Johnson, Topics in Matrix Analysis (Cambridge U. Press, 1991).
[CrossRef]

L. Yaroslavsky, “Fast discrete sinc-interpolation: a gold standard for image resampling,” in Advances in Signal Transforms: Theory and Application, J.Astola and L.Yaroslavsky, eds., EURASIP Book Series on Signal Processing and Communications (Hindawi, 2007), pp. 337-405.

E. Margolis and Y. C. Eldar, “Interpolation with non-uniform B-splines,” in Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (IEEE, 2004), Vol. 2, pp. 577-580.

P. J. S. G. Ferreira, “Iterative and noniterative recovery of missing samples for 1-D band-limited signals,” in Nonuniform Sampling, F.Marvasti, ed. (Kluwer Academic/Plenum, 2001), pp. 235-278.
[CrossRef]

M. Hasan and F. Marvasti, “Application of nonuniform sampling to error concealment,” in Nonuniform Sampling, F.Marvasti, ed. (Kluwer Academic/Plenum, 2001), pp. 619-646.

A. Averbuch, R. Coifman, M. Israeli, I. Sidelnikov, and Y. Shkolinsky, “Irregular sampling for multi-dimensional polar processing of integral transforms,” in Advances in Signal Transforms: Theory and Applications, J.Astola and L.Yaroslavsky, eds. (Hindawi, 2007), pp. 143-198.

A. Averbuch and V. Zheludev, “Wavelet and frame transforms originated from continuous and discrete splines,” in Advances in Signal Transforms: Theory and Applications, J.Astola and L.Yaroslavsky, eds. (Hindawi, 2007), pp. 1-54.

Compressed sensing resources: http://www.dsp.ece.rice.edu/cs/. Last accessed December 18, 2008.

Y. Katiyi and L. Yaroslavsky, “Regular matrix methods for synthesis of fast transforms: general pruned and integer-to-integer transforms,” in Proceedings of IEEE International Workshop on Spectral Methods and Multirate Signal Processing (IEEE, 2001), pp. 17-24.

Y. Katiyi and L. Yaroslavsky, “V/HS structure for transforms and their fast algorithms,” in Proceedings of the IEEE 3rd International Symposium on Signal Processing and Analysis (IEEE, 2003), Vol. 1, pp. 482--487.

L. Yaroslavsky, Digital Holography and Digital Signal Processing (Kluwer Academic, 2004).

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

Fig. 1
Fig. 1

Flow diagram of the iterative signal recovery procedure.

Fig. 2
Fig. 2

Restoration of a DFT low-pass band-limited signal by matrix inversion for the cases of (a) random and (b) compactly placed signal samples and (c) restoration by the iterative algorithm. Plot (d) shows the standard deviation of the signal restoration error as a function of the number of iterations. The experiment was conducted for test signal length of 64 samples; bandwidth of 13 frequency samples ( 1 5 of the signal base band).

Fig. 3
Fig. 3

Recovery of an image band limited in the DCT domain by a square: (a) initial image with 3136 “randomly” placed samples in positions shown by white dots; (b) the shape of the image spectrum in the DCT domain; (c) image restored by the iterative algorithm after 100,000 iterations with restoration peak signal-to-error standard deviation (PSNR) 4230; (d) image restored by B-spline interpolation with restoration PSNR 966; (e) iterative algorithm restoration error (white, large errors; black, small errors); (f) restoration error standard deviation versus number of iterations for the iterative algorithm and that for the B-spline interpolation.

Fig. 4
Fig. 4

Recovery of an image band limited in the DCT domain by a circle sector: (a) initial image with 3964 “randomly” placed samples in positions shown by white dots; (b) the shape of the image spectrum in the DCT domain; (c) image restored by the iterative algorithm after 100,000 iterations with restoration PSNR 21.5; (d) image restored by B-spline interpolation with restoration PSNR 7.42; (e) iterative algorithm restoration error (white, large errors; black, small errors); (f) restoration error standard deviation versus number of iterations of the iterative algorithm for the iterative algorithm and that for the B-spline interpolation.

Fig. 5
Fig. 5

Recovery of an image band-limited in the DCT domain by a circle sector from its level lines: (a) initial image with level lines (shown by white lines); (b) image restored by the iterative algorithm after 1,000 iterations with restoration PSNR 35,000 (note that the restoration error is concentrated in a small area of the image); (c) image restored by B-spline interpolation with restoration PSNR 29.4; (d) iterative algorithm restoration error (white, large errors; black, small errors); (e) restoration error standard deviation versus number of iterations for the iterative algorithm and that for the B-spline interpolation.

Fig. 6
Fig. 6

First eight basis functions of the 64-point (a) Haar and (b) Walsh transforms. Intervals of function constancy are outlined by dashed–dotted lines. Functions that belong to the same scale are outlined by dashed boxes.

Fig. 7
Fig. 7

Two cases of sparse sampling of an image band-limited in the Haar transform: (a) not-recoverable case, (b) recoverable case (sample points are marked with dots). Image size 64 × 64   pixels ; band limitation 8 × 8 (scale 3).

Fig. 8
Fig. 8

Example of perfect reconstruction in the Walsh domain.

Fig. 9
Fig. 9

Iterative image interpolation in the superresolution process: (a) a low-resolution frame, (b) image fused by elastic image registration from 50 frames, (c) the result of iterative interpolation of image (b) after 50 iterations.

Fig. 10
Fig. 10

Recovery of missing samples of a sinogram: (a) original image and (b) its Radon transform (sinogram), (c) image reconstructed from the sinogram, (d) image corrupted by the loss of 55% of its randomly selected samples; (e) a sinogram recovered from (d) using the iterative band-limited interpolation algorithm, and (f) plot of the standard deviation of the slice reconstruction error as a function of the iteration number.

Fig. 11
Fig. 11

Recovery of missing image projections: (a) original projections (sinogram) of the test image of Fig. 10a, (b) sinogram with every second projection removed, (c) sinogram recovered from (b) using the iterative interpolation algorithm, and (d) plot of the standard deviation of the image reconstruction error as a function of the iteration number.

Equations (20)

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

Φ N = { φ r ( k ) } r = 0 , 1 , , N 1
A N = Φ N Γ N = { r = 0 N 1 γ r φ r ( k ) } k = 0 , 1 , N 1
{ a k = r = 0 N 1 γ r φ r ( k ) } k K ̃
A ̂ N BL = { a ̂ k = r ̃ R ̃ γ r ̃ φ r ̃ ( k ) } .
A ̂ N BL = { a ̂ k = r = 0 N 1 γ ̃ r φ r ( k ) } ,
γ ̃ r = { γ r , r R ̃ 0 , otherwise } .
A ̃ K = K o f N Φ Γ ̃ K = { a k ̃ = r ̃ R ̃ γ r ̃ φ r ̃ ( k ̃ ) } ,
Γ ̃ K = { γ ̃ r } = K of N Φ 1 A ̃ K ,
MSE = A N A ̂ N 2 = k = 0 N 1 a k a ̂ k 2 = r R γ r 2 .
K of N DFT LP = { exp ( i 2 π k ̃ r ̃ LP N ) }
r ̃ LP R ̃ LP = { [ 0 , 1 , , ( K 1 ) 2 , N ( K 1 ) 2 , , N 1 ] } .
r ͌ R ͌ = { [ N ( K 1 ) 2 , , N 1 , 0 , 1 , , ( K 1 ) 2 ] }
K of N DFT DFTsh = { exp [ i 2 π k ̃ r ͌ N ] } = { exp [ i 2 π N ( K 1 ) 2 N k ̃ ] δ ( k ̃ r ̃ ̃ ̃ ) } { exp [ i 2 π k ̃ r ̃ ̃ ̃ N ] } ,
r ̃ ̃ ̃ R ̃ ̃ ̃ = { [ 0 , , K 1 ] } .
K of N DFT HP = { exp ( i 2 π k ̃ r ̃ HP N ) } ,
r ̃ HP R ̃ HP = { [ ( N K + 1 ) 2 , ( N K + 3 ) 2 , , ( N + K 1 ) 2 ] } ,
r ̃ mLP R ̃ mLP = { 0 , m , , m ( K 1 ) 2 , N m ( K 1 ) 2 , , N m ( K 1 ) 2 + ( K + 1 ) 2 } .
K of N SDFT = { exp ( i 2 π ( k ̃ + 1 2 ) r ̃ 2 N ) }
K of N SDFT = { exp ( i 2 π k ̃ r ̃ 2 N ) { exp ( i π r ̃ 2 N ) δ ( k r ) } } = K of N DFT { exp ( i π r ̃ 2 N ) δ ( k r ) }
K of N Walsh K = 5 = [ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ] ,

Metrics