##### Document Text Contents

Page 1

SPARSE IMAGE REPRESENTATION

VIA COMBINED TRANSFORMS

a dissertation

submitted to the department of statistics

and the committee on graduate studies

of stanford university

in partial fulfillment of the requirements

for the degree of

doctor of philosophy

Xiaoming Huo

August 1999

Page 2

c© Copyright by Xiaoming Huo 1999

All Rights Reserved

ii

Page 105

3.7. PROOFS 77

the ijth component of matrix Σ is

Σij =

N−1∑

k=0

λkα

2

1(k)α2(i)α2(j)

2

N

cos

(

π(k + δ1)(i + δ2)

N

)

cos

(

π(k + δ1)(j + δ2)

N

)

= α2(i)α2(j)

1

N

N−1∑

k=0

λkα

2

1(k)

[

cos

π(k + δ1)(i − j)

N

+ cos

π(k + δ1)(i + j + 2δ2)

N

]

.

In the above equation, let the first term 1

N

∑N−1

k=0 λkα

2

1(k) cos

π(k+δ1)(i−j)

N

be the ijth

element of matrix Σ1, and let the second term 1N

∑N−1

k=0 λkα

2

1(k) cos

π(k+δ1)(i+j+2δ2)

N

be the

ijth element of matrix Σ2. It is easy to see that the matrix Σ1 is Toeplitz, and the matrix

Σ2 is Hankel. Inserting different values of δ1 and δ2, we establish the Theorem 3.5.

Proof of Theorem 3.6

Consider the z-transform of sequence {h(n) : n ∈ Z} and sequence {g(n) : n ∈ Z}:

H(z) =

∑

n∈Z

h(n)zn,

G(z) =

∑

n∈Z

g(n)zn.

From (3.27), note that all the even terms in H(z)H(z−1) have zero coefficient except the

constant term. Hence we have

H(z)H(z−1) + H(−z)H(−z−1) = 2. (3.38)

Similarly from (3.28) we have

G(z)G(z−1) + G(−z)G(−z−1) = 2. (3.39)

From (3.29), all the even terms in H(z)G(z−1) have zero coefficients, so we have

G(z)H(z−1) + G(−z)H(−z−1) = 0. (3.40)

Page 106

78 CHAPTER 3. IMAGE TRANSFORMS AND IMAGE FEATURES

Equations (3.38) (3.39) and (3.40) together are equivalent to the matrix multiplication

(

H(z) H(−z)

G(z) G(−z)

)(

H(z−1) H(−z−1)

G(z−1) G(−z−1)

)

=

(

2 0

0 2

)

.

Taking the determinant of both sides, we have

[H(z)G(−z) − G(z)H(−z)][H(z−1)G(−z−1) − G(z−1)H(−z−1)] = 4. (3.41)

If both sequence {h(n) : n ∈ Z} and sequence {g(n) : n ∈ Z} have finite length (thinking of

the impulse responses of FIR filters), then the polynomial H(z)G(−z) − G(z)H(−z) must

have only one nonzero term. Since if the polynomial H(z)G(−z) − G(z)H(−z) has more

than two terms and simultaneously has finite length, (3.41) can never be equal to a constant.

On the other hand, we have

[H(z−1) + H(−z−1)][H(z)G(−z) − G(z)H(−z)]

= H(z−1)H(z)G(−z) + H(−z−1)H(z)G(−z)

−H(z−1)G(z)H(−z) − H(−z−1)G(z)H(−z)

(3.40)

= H(z−1)H(z)G(−z) − H(z−1)H(z)G(z)

+H(−z−1)G(−z)H(−z) − H(−z−1)G(z)H(−z)

(3.38)

= 2[G(−z) − G(z)].

We know that H(z)G(−z) − G(z)H(−z) only has one nonzero term. The polynomial

H(z−1)+H(−z−1) can only have terms with even exponents and polynomial G(−z)−G(z)

can only have terms with odd exponents, so from the previous equation, there must exist

an integer k, such that

H(z)G(−z) − G(z)H(−z) = 2z2k+1,

and

[H(z−1) + H(−z−1)]z2k+1 = G(−z) − G(z). (3.42)

Page 209

BIBLIOGRAPHY 181

[127] C. E. Shannon. A mathematical theory of communication. Bell System Technical

Journal, 27:379–423, 623–56, October 1948.

[128] J. E. Spingarn. Partial inverse of a monotone operator. Applied Mathematics and

Optimization, 10:247–65, 1983.

[129] Frank Spitzer. Markov random fields and Gibbs ensembles. American Mathematical

Monthly, 78:142–54, February 1971.

[130] A.S. Stern, D.L Donoho, and Hoch J.C. Iterative thresholding and minimum �1-norm

reconstruction. based on personal communication, 1996 or later.

[131] Mann Steve and Simon Haykin. Adaptive “chirplet” transform: an adaptive general-

ization of the wavelet transform. Optical Engineering, 31(6):1243–56, June 1992.

[132] Gilbert Strang. Wavelets and Filter Banks. Wellesley-Cambridge Press, 1996.

[133] Robert Tibshirani. Regression shrinkage and selection via the LASSO. J. the Royal

Statistical Society, Series B, 58:267–288, 1996.

[134] Richard Tolimieri, Myoung An, and Chao Lu. Algorithms for Discrete Fourier Trans-

form and Convolution. Springer, 2nd edition, 1997.

[135] Paul Tseng. Dual coordinate ascent methods for non-strictly convex minimization.

Mathematical Programming, 59:231–47, 1993.

[136] Charles Van Loan. Computational Frameworks for the Fast Fourier Transform. SIAM,

1992.

[137] R. J. Vanderbei. Linear Programming. Kluwer Academic Publishers, 1996.

[138] S. Vembu, S. Verdú, and Y. Steinberg. The source-channel separation theorem revis-

ited. IEEE Trans. on Inform. Theory, 41(1):44–54, Jan. 1995.

[139] Z. Wang and B.R. Hunt. Comparative performance of two different versions of the

discrete cosine transform. IEEE Transactions on Acoustics, Speech and Signal Pro-

cessing, ASSP-32(2):450–3, 1984.

[140] Zhongde Wang. Reconsideration of “a fast computational algorithm for the discrete

cosine transform”. IEEE Transactions on Communications, Com-31(1):121–3, Jan.

1983.

Page 210

182 BIBLIOGRAPHY

[141] Mladen Victor Wickerhauser. Smooth localized orthonormal bases. Comptes Rendus

de l’Académie des Sciences de Paris, 316:423–7, 1993.

[142] Mladen Victor Wickerhauser. Adapted wavelet analysis from theory to software.

Wellesley, 1994.

[143] S. Winograd. On computing the discrete fourier transform. Mathematics of Compu-

tation, 32(141):175–99, 1978.

[144] Margaret H. Wright. The interior-point revolution in constrained optimization. Tech-

nical Report 98-4-09, Bell Laboratories, Murray Hill, New Jersey 07974, June 1998.

“http://cm.bell-labs.com/cm/cs/doc/98/4-09.ps.gz”.

[145] Song Chun Zhu, Yingnian Wu, and David Mumford. Filters, random fields and max-

imum entropy (frame): towards a unified theory for texture modeling. International

J. Computer Vision, 27(2):107–26, 1998.

SPARSE IMAGE REPRESENTATION

VIA COMBINED TRANSFORMS

a dissertation

submitted to the department of statistics

and the committee on graduate studies

of stanford university

in partial fulfillment of the requirements

for the degree of

doctor of philosophy

Xiaoming Huo

August 1999

Page 2

c© Copyright by Xiaoming Huo 1999

All Rights Reserved

ii

Page 105

3.7. PROOFS 77

the ijth component of matrix Σ is

Σij =

N−1∑

k=0

λkα

2

1(k)α2(i)α2(j)

2

N

cos

(

π(k + δ1)(i + δ2)

N

)

cos

(

π(k + δ1)(j + δ2)

N

)

= α2(i)α2(j)

1

N

N−1∑

k=0

λkα

2

1(k)

[

cos

π(k + δ1)(i − j)

N

+ cos

π(k + δ1)(i + j + 2δ2)

N

]

.

In the above equation, let the first term 1

N

∑N−1

k=0 λkα

2

1(k) cos

π(k+δ1)(i−j)

N

be the ijth

element of matrix Σ1, and let the second term 1N

∑N−1

k=0 λkα

2

1(k) cos

π(k+δ1)(i+j+2δ2)

N

be the

ijth element of matrix Σ2. It is easy to see that the matrix Σ1 is Toeplitz, and the matrix

Σ2 is Hankel. Inserting different values of δ1 and δ2, we establish the Theorem 3.5.

Proof of Theorem 3.6

Consider the z-transform of sequence {h(n) : n ∈ Z} and sequence {g(n) : n ∈ Z}:

H(z) =

∑

n∈Z

h(n)zn,

G(z) =

∑

n∈Z

g(n)zn.

From (3.27), note that all the even terms in H(z)H(z−1) have zero coefficient except the

constant term. Hence we have

H(z)H(z−1) + H(−z)H(−z−1) = 2. (3.38)

Similarly from (3.28) we have

G(z)G(z−1) + G(−z)G(−z−1) = 2. (3.39)

From (3.29), all the even terms in H(z)G(z−1) have zero coefficients, so we have

G(z)H(z−1) + G(−z)H(−z−1) = 0. (3.40)

Page 106

78 CHAPTER 3. IMAGE TRANSFORMS AND IMAGE FEATURES

Equations (3.38) (3.39) and (3.40) together are equivalent to the matrix multiplication

(

H(z) H(−z)

G(z) G(−z)

)(

H(z−1) H(−z−1)

G(z−1) G(−z−1)

)

=

(

2 0

0 2

)

.

Taking the determinant of both sides, we have

[H(z)G(−z) − G(z)H(−z)][H(z−1)G(−z−1) − G(z−1)H(−z−1)] = 4. (3.41)

If both sequence {h(n) : n ∈ Z} and sequence {g(n) : n ∈ Z} have finite length (thinking of

the impulse responses of FIR filters), then the polynomial H(z)G(−z) − G(z)H(−z) must

have only one nonzero term. Since if the polynomial H(z)G(−z) − G(z)H(−z) has more

than two terms and simultaneously has finite length, (3.41) can never be equal to a constant.

On the other hand, we have

[H(z−1) + H(−z−1)][H(z)G(−z) − G(z)H(−z)]

= H(z−1)H(z)G(−z) + H(−z−1)H(z)G(−z)

−H(z−1)G(z)H(−z) − H(−z−1)G(z)H(−z)

(3.40)

= H(z−1)H(z)G(−z) − H(z−1)H(z)G(z)

+H(−z−1)G(−z)H(−z) − H(−z−1)G(z)H(−z)

(3.38)

= 2[G(−z) − G(z)].

We know that H(z)G(−z) − G(z)H(−z) only has one nonzero term. The polynomial

H(z−1)+H(−z−1) can only have terms with even exponents and polynomial G(−z)−G(z)

can only have terms with odd exponents, so from the previous equation, there must exist

an integer k, such that

H(z)G(−z) − G(z)H(−z) = 2z2k+1,

and

[H(z−1) + H(−z−1)]z2k+1 = G(−z) − G(z). (3.42)

Page 209

BIBLIOGRAPHY 181

[127] C. E. Shannon. A mathematical theory of communication. Bell System Technical

Journal, 27:379–423, 623–56, October 1948.

[128] J. E. Spingarn. Partial inverse of a monotone operator. Applied Mathematics and

Optimization, 10:247–65, 1983.

[129] Frank Spitzer. Markov random fields and Gibbs ensembles. American Mathematical

Monthly, 78:142–54, February 1971.

[130] A.S. Stern, D.L Donoho, and Hoch J.C. Iterative thresholding and minimum �1-norm

reconstruction. based on personal communication, 1996 or later.

[131] Mann Steve and Simon Haykin. Adaptive “chirplet” transform: an adaptive general-

ization of the wavelet transform. Optical Engineering, 31(6):1243–56, June 1992.

[132] Gilbert Strang. Wavelets and Filter Banks. Wellesley-Cambridge Press, 1996.

[133] Robert Tibshirani. Regression shrinkage and selection via the LASSO. J. the Royal

Statistical Society, Series B, 58:267–288, 1996.

[134] Richard Tolimieri, Myoung An, and Chao Lu. Algorithms for Discrete Fourier Trans-

form and Convolution. Springer, 2nd edition, 1997.

[135] Paul Tseng. Dual coordinate ascent methods for non-strictly convex minimization.

Mathematical Programming, 59:231–47, 1993.

[136] Charles Van Loan. Computational Frameworks for the Fast Fourier Transform. SIAM,

1992.

[137] R. J. Vanderbei. Linear Programming. Kluwer Academic Publishers, 1996.

[138] S. Vembu, S. Verdú, and Y. Steinberg. The source-channel separation theorem revis-

ited. IEEE Trans. on Inform. Theory, 41(1):44–54, Jan. 1995.

[139] Z. Wang and B.R. Hunt. Comparative performance of two different versions of the

discrete cosine transform. IEEE Transactions on Acoustics, Speech and Signal Pro-

cessing, ASSP-32(2):450–3, 1984.

[140] Zhongde Wang. Reconsideration of “a fast computational algorithm for the discrete

cosine transform”. IEEE Transactions on Communications, Com-31(1):121–3, Jan.

1983.

Page 210

182 BIBLIOGRAPHY

[141] Mladen Victor Wickerhauser. Smooth localized orthonormal bases. Comptes Rendus

de l’Académie des Sciences de Paris, 316:423–7, 1993.

[142] Mladen Victor Wickerhauser. Adapted wavelet analysis from theory to software.

Wellesley, 1994.

[143] S. Winograd. On computing the discrete fourier transform. Mathematics of Compu-

tation, 32(141):175–99, 1978.

[144] Margaret H. Wright. The interior-point revolution in constrained optimization. Tech-

nical Report 98-4-09, Bell Laboratories, Murray Hill, New Jersey 07974, June 1998.

“http://cm.bell-labs.com/cm/cs/doc/98/4-09.ps.gz”.

[145] Song Chun Zhu, Yingnian Wu, and David Mumford. Filters, random fields and max-

imum entropy (frame): towards a unified theory for texture modeling. International

J. Computer Vision, 27(2):107–26, 1998.