# Patent

## Title
Quantization method and apparatus

## Abstract

Quantization for oversampled signals with an error minimization searches based upon clusters of possible sampling vectors where the clusters have minimal correlation and thereby decrease reconstruction error as a function of oversampling (redundancy) ratio.

## Background
CROSS-REFERENCE TO RELATED APPLICATIONS
This application is a divisional of application Ser. No. 12/184,873, filed Aug. 1, 2008 and claims the priority of U.S. provisional application Ser. No. 60/954,526, filed Aug. 7, 2007, the contents of which are herein incorporated by reference in their entirety.


BACKGROUND OF THE INVENTION
The present invention relates to digital signal processing, and more particularly to architectures and methods for oversampling quantization such as in analog-to-digital conversion.
Analog-to-digital converters (ADCs) are used to convert analog signals, such as music or voice, to digital format to allow for compression (e.g., MP3) and transmission over digital networks. An ADC samples an input analog signal (makes discrete in time) and quantizes the samples (makes discrete in amplitude) to give a sequence of digital words. For playback, a digital-to-analog converter (DAC) reconstructs (approximately) the input analog signal from the sequence of digital words. If the sampling rate of the ADC is higher than the Nyquist rate for the input analog signal, then the sampling is essentially reversible; whereas, the quantization always loses information. Thus ADC have a problem of optimal quantization.
A commonly used type of ADC includes oversampling plus a sigma-delta modulator; FIG. 3A illustrates one possible implementation of a one-stage modulator and quantizer. In particular, input signal x(t) is oversampled to give the input digital sequence x(nT) which will be quantized to give the output quantized digital sequence y(nT). The modulator operation includes subtracting a scaled and delayed quantization error, c e((n−1)T), from the input samples prior to quantization; this feedback provides integration of the overall quantization error. That is,

y(nT)=Q(u(nT))

e(nT)=y(nT)−u(nT)

u(nT)=x(nT)−c e((n−1)T)

Recursive substitution gives:

e(nT)=y(nT)−x(nT)+c[y((n−1)T)−x((n−1)T)]++ . . . +ck[y((n−k)T)−x((n−k)T)]+

See Boufounos and Oppenheim, Quantization Noise Shaping on Arbitrary Frame Expansion, Proc. ICASSP, vol. 4, pp. 205-208 (2005) which notes an optimal value for the scaling constant c as sin c(1/r) where r is the oversampling ratio.

SUMMARY OF THE INVENTION
The present invention provides quantization for oversampled signals with an error minimization search based on clusters of possible sampling vectors.



BRIEF DESCRIPTION OF THE DRAWINGS
FIGS. 1A-1B illustrate a preferred embodiment system and method.
FIGS. 2A-2B are experimental results.
FIGS. 3A-3C show an ADC, a processor, and network communication.



DESCRIPTION OF THE PREFERRED EMBODIMENTS
1. Overview
Preferred embodiment oversampling quantization methods cluster possible quantization vectors according to correlations and search clusters to determine quantization to minimize reconstruction errors. FIG. 1A shows functional blocks of a system (e.g., an ADC) using the quantization method.
Preferred embodiment systems (pipelined delta-sigma analog-to-digital converters, etc.) perform preferred embodiment methods with any of several types of hardware: digital signal processors (DSPs), general purpose programmable processors, application specific circuits, or systems on a chip (SoC) such as combinations of a DSP and a RISC processor together with various specialized programmable accelerators. FIG. 3B is an example of digital camera hardware including various ADCs. A stored program in an onboard or external (flash EEP)ROM or FRAM could implement the signal processing. Preferred embodiment analog-to-digital converters and digital-to-analog converters can provide coupling to the real world, modulators and demodulators (plus antennas for air interfaces) can provide coupling for transmission waveforms, and packetizers can provide formats for transmission over networks such as the Internet; see FIG. 3C.
2. Sampling Theorem Background
Preliminarily, recall that the sampling theorem provides for exact reconstruction of x(t), a finite-energy and bandwidth-limited signal, from samples taken at the Nyquist rate or a higher rate. In particular, with x(t) in the subspace of L2(R) of functions with spectrum limited to −1/(2T)<f<1/(2T) where f is the frequency variable and T is a sampling interval (so the sampling rate is 1/T):

x(t)=Σnεzx(nT)sin c(t/T−n)

where sin c(u)=sin(πu)/πu and Z denotes the set of integers.

The samples can be written in terms of an inner product in L2(R) as follows. Let X(f) be the Fourier transform of x(t); then using the limit on the bandwidth of x(t) gives




  
    
      
        
          x
          ⁡
          
            (
            
              n
              ⁢
              
                
              
              ⁢
              T
            
            )
          
        
        =
        
        ⁢
        
          
            ∫
            
              
                -
                ∞
              
              ,
              ∞
            
            
              
            
          
          ⁢
          
            
              X
              ⁡
              
                (
                f
                )
              
            
            ⁢
            
              e
              
                2
                ⁢
                π
                ⁢
                
                  
                
                ⁢
                i
                ⁢
                
                  
                
                ⁢
                fnT
              
            
            ⁢
            
              
            
            ⁢
            
              d
              f
            
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            ∫
            
              
                -
                ∞
              
              ,
              ∞
            
            
              
            
          
          ⁢
          
            
              X
              ⁡
              
                (
                f
                )
              
            
            ⁢
            
              rect
              ⁡
              
                (
                fT
                )
              
            
            ⁢
            
              e
              
                2
                ⁢
                π
                ⁢
                
                  
                
                ⁢
                i
                ⁢
                
                  
                
                ⁢
                fnT
              
            
            ⁢
            
              
            
            ⁢
            
              d
              f
            
          
        
      
    
  




where rect(u) denotes the rectangle function which equals 1 for −1⁄2<u<1⁄2 and 0 elsewhere. Then applying Parseval's theorem gives:

x(nT)=∫−∞, ∞ x(t)(1/T)sin c(t/T−n)dt 

where we used the Fourier transform of (1/T)sin c(t/T−n) is rect(fT)e−2πi f nT. Then the integral can be interpreted as the inner product in L2(R):

x(nT)=x(t)|(1/T)sin c(t/T−n)

Note that the functions sin c(t/T−n) are orthogonal:




  
    
      
        
          〈
          
            
              sin
              ⁢
              
                
              
              ⁢
              
                c
                ⁡
                
                  (
                  
                    
                      t
                      /
                      T
                    
                    -
                    m
                  
                  )
                
              
            
            ❘
            
              sin
              ⁢
              
                
              
              ⁢
              
                c
                ⁡
                
                  (
                  
                    
                      t
                      /
                      T
                    
                    -
                    n
                  
                  )
                
              
            
          
          〉
        
        =
        
        ⁢
        
          
            T
            2
          
          ⁢
          
            
              ∫
              
                
                  -
                  ∞
                
                ,
                ∞
              
              
                
              
            
            ⁢
            
              
                rect
                ⁡
                
                  (
                  fT
                  )
                
              
              ⁢
              
                e
                
                  
                    -
                    2
                  
                  ⁢
                  π
                  ⁢
                  
                    
                  
                  ⁢
                  i
                  ⁢
                  
                    
                  
                  ⁢
                  fmT
                
              
            
          
        
      
    
  
  
    
      
        
        ⁢
        
          rect
          ⁢
          
            (
            fT
            )
          
          ⁢
          
            e
            
              2
              ⁢
              π
              ⁢
              
                
              
              ⁢
              i
              ⁢
              
                
              
              ⁢
              fnT
            
          
          ⁢
          
            
          
          ⁢
          
            d
            f
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            T
            2
          
          ⁢
          
            
              ∫
              
                
                  -
                  ∞
                
                ,
                ∞
              
              
                
              
            
            ⁢
            
              
                rect
                ⁡
                
                  (
                  fT
                  )
                
              
              ⁢
              
                e
                
                  
                    -
                    2
                  
                  ⁢
                  π
                  ⁢
                  
                    
                  
                  ⁢
                  i
                  ⁢
                  
                    
                  
                  ⁢
                  
                    f
                    ⁡
                    
                      (
                      
                        n
                        -
                        m
                      
                      )
                    
                  
                  ⁢
                  T
                
              
              ⁢
              
                d
                f
              
            
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          T
          ⁢
          
            
          
          ⁢
          sin
          ⁢
          
            
          
          ⁢
          
            c
            ⁡
            
              (
              
                n
                -
                m
              
              )
            
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          T
          ⁢
          
            
          
          ⁢
          
            δ
            
              m
              ,
              n
            
          
        
      
    
  




Thus the sampling theorem states that the set of functions sin c(t/T n) for n=0, ±1, ±2, . . . constitutes an orthogonal basis for H, the subspace of L2(R) consisting of functions with spectrum in 1/(2T)<f<1/(2T). That is, the sampling theorem for H provides:

x(t)=ΣnεZx(.)|φanalysis, n(.)φsyntheses, n(t)

where the synthesis functions are φsynthesis, n(t)=sin c(t/T−n) and the analysis functions are φanalysis, n(t)=(1/T)sin c(t/T−n) for the space of bandlimited signals.

This may also be interpreted as the analysis linear mapping F: H→l2(Z) with F(x(t))=x where the components of vector x, xn=x(t)|φanalysis, n(t), are the samples of x(t), together with the adjoint synthesis linear mapping F*: l2(Z)→H defined by F*(c)=ΣnεZ cn φsynthesis, n(t). Of course, F is one-to-one but not onto, F* is not one-to-one, and the operator norm of F depends upon the sampling rate: ∥F(x(t))∥2=(1/T)∥x(t)∥2.
3. Oversampling
For sampling x(t) in H at rates higher than the Nyquist rate, such as oversampling by a (redundancy) factor of r>1, the corresponding samples, x(nT/r), could still be expressed as inner products of x(t) with the corresponding analysis functions (1/T)sin c(t/T−n/r), and x(t) could still be expanded as a sum of synthesis functions (1/r)sin c(t/T−n/r) where the 1/r factor comes from the fact that each of r subsets of the functions sin c(t/T−n/r) with the same n mod r suffices (by the sampling theorem) to reconstruction x(t) and so the total sum gives r times x(t). However, these sets of functions are overcomplete in the sense that the expansion coefficients are not unique for x(t) in H, and the functions no longer form orthogonal sets:

sin c(t/T−m/r)sin c(t/T−n/r)=T sin c(n/r−m/r)

As a simple example, for r=2 and T=1 the analysis functions are the sin c(t−n/2). Then the samples of x(t) at integers and half-integers are:

x(m)=x(t)−sin c(t−m)

x(m+1⁄2)=x(t)sin c(t−(m+1⁄2))

The sampling theorem provides that each of these sets of samples is sufficient for reconstruction:




  
    
      
        
          
            x
            ⁡
            
              (
              t
              )
            
          
          =
          
          ⁢
          
            
              ∑
              
                m
                ∈
                Z
              
              
                
              
            
            ⁢
            
              
            
            ⁢
            
              
                x
                ⁡
                
                  (
                  m
                  )
                
              
              ⁢
              sin
              ⁢
              
                
              
              ⁢
              
                c
                ⁡
                
                  (
                  
                    t
                    -
                    m
                  
                  )
                
              
            
          
        
      
    
    
      
        
          =
          
          ⁢
          
            
              ∑
              
                m
                ∈
                Z
              
              
                
              
            
            ⁢
            
              
            
            ⁢
            
              2
              ⁢
              
                x
                ⁡
                
                  (
                  m
                  )
                
              
              ⁢
              
                (
                
                  1
                  /
                  2
                
                )
              
              ⁢
              sin
              ⁢
              
                
              
              ⁢
              
                c
                ⁡
                
                  (
                  
                    t
                    -
                    m
                  
                  )
                
              
            
          
        
      
    
  




  
    
      
        
          
            x
            ⁡
            
              (
              t
              )
            
          
          =
          
          ⁢
          
            
              ∑
              
                m
                ∈
                Z
              
              
                
              
            
            ⁢
            
              
            
            ⁢
            
              
                x
                ⁡
                
                  (
                  
                    m
                    +
                    
                      1
                      /
                      2
                    
                  
                  )
                
              
              ⁢
              sin
              ⁢
              
                
              
              ⁢
              
                c
                ⁡
                
                  (
                  
                    t
                    -
                    
                      (
                      
                        m
                        +
                        
                          1
                          /
                          2
                        
                      
                      )
                    
                  
                  )
                
              
            
          
        
      
    
    
      
        
          =
          
          ⁢
          
            
              ∑
              
                m
                ∈
                Z
              
              
                
              
            
            ⁢
            
              
            
            ⁢
            
              2
              ⁢
              
                x
                ⁡
                
                  (
                  
                    m
                    +
                    
                      1
                      /
                      2
                    
                  
                  )
                
              
              ⁢
              
                (
                
                  1
                  /
                  2
                
                )
              
              ⁢
              sin
              ⁢
              
                
              
              ⁢
              
                c
                ⁡
                
                  (
                  
                    t
                    -
                    
                      (
                      
                        m
                        +
                        
                          1
                          /
                          2
                        
                      
                      )
                    
                  
                  )
                
              
            
          
        
      
    
  



Thus the expansion in terms of the overcomplete set is not unique; indeed

x(t)=Σn εZ cn(1⁄2)sin c(t−n/2)

where a first possible set of expansion coefficients is: cn=x(n/2) (which is the vector F(x(t))), a second possible set is cn=2x(n/2) for n even and cn=0 for n odd; and a third possible set is: cn=0 for n even and cn=2x(n/2) for n odd. In fact, the set of expansion coefficients cn=x(n/2) for n even and cn=x(n/2) for n odd makes the sum 0; that is, Σn εZ(−1)n x(n/2)(1⁄2)sin c(t−n/2)=0.

4. Frames

In general, let H denote L2(R) or a subspace of L2(R); then a set {φj}jεJ is a frame of H if there exist two positive numbers A1, A2 such that for any x in H we have

A1∥x∥2≦ΣjεJ|x|φj|2≦a2∥x∥2 

A frame is called “tight” when A1=A2. The examples of the preceding sections, φj=sin c(t/T−j/r), are tight frames with A=rT . Frames can be viewed as a generalization of bases of a Hilbert space. If {φj}jεJ is a frame, then any element x in H can be expressed as

x=Σjεj cj φj 

where the expansion coefficients c={cj}jεJ may be considered an element of l2(Z) but may not be unique if the frame is overcomplete, such as for the example of preceding section 3.

The frame analysis operator, F: H→l2(Z), and its adjoint (frame synthesis) operator, F*: l2(Z)→H, are defined by:

F(x)={x|φj}jεJ 

F*(c)=ΣjεJ cj φj 

Note that when h={hj}jεJ is in ker(F*), the kernel (null space) of F*, then c+h also is a set of expansion coefficients for x:

x=ΣjεJ(cj+hj)φj 

Of course, h being in ker(F*) is the same as h being perpendicular to ran(F), the range of F, in l2(Z). Note that ran(F) is the subspace of vectors which consist of samples of functions in H.

Define the frame operator, F*F: H→H, so F*F(x)=ΣjεJx|φjφj. Then the dual frame, {φdual j}jεJ, is defined as the frame operator inverse image of the frame:

φdual.j=(F*F)−1 φj 

For tight frames we have φdual.j=φj/A where A is the frame bound.

One possible set of expansion coefficients of particular importance is the minimum-norm-in-l2(Z) solution, which is computed as:

ĉj=x|φdual

Any other set of expansion coefficients for x can be expressed as

c=ĉ+Σn γn v(n) 

where the v(n) form an orthonormal basis for ker(F*) as a subspace of l2(Z).

5. Quantization for Reconstruction

Quantization of samples for an oversampling ADC corresponds to quantization of expansion coefficients of the signal x(t) with respect to the frame corresponding to the oversampling (e.g., sin c(t/T−n/r)); and the preferred embodiment methods minimize the reconstruction error due to the quantization of the frame expansion coefficients. First, define the quantization error for vector c in l2(Z) as the vector Qerror(c) in l2(Z)

Qerror(c)=c+Σn γn v(n)−(└c┘+α)

where └.┘ denotes the floor function (largest integer not greater than) and α is an integer vector that corresponds to the quantization approximation. For example, when Q(cj)=└cj┘, then αj=0; whereas, when Q(cj)=┌cj┐, then αj=1. ┌.┐ denotes the ceiling function (smallest integer not less than), and the cj are presumed normalized by the quantization step size. In effect, Q(cj)=└cj┘+αj, and Qerror(c)=c−Q(c)+Σn γn v(n) where, as before, the v(n) form an orthonormal basis for ker(F*). Let

e=c−└c┘

so e is the integer truncation error vector. Then the reconstruction error in H is:





  
    
      
        
          e
          
            (
            rec
            )
          
        
        =
        
        ⁢
        
          F
          *
          
            (
            
              
                Q
                error
              
              ⁡
              
                (
                c
                )
              
            
            )
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          F
          *
          
            (
            
              e
              -
              α
            
            )
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            ∑
            
              j
              ∈
              J
            
            
              
            
          
          ⁢
          
            
          
          ⁢
          
            
              (
              
                
                  e
                  j
                
                -
                
                  α
                  j
                
              
              )
            
            ⁢
            
              φ
              j
            
          
        
      
    
  




Therefore the reconstruction optimization problem can be written as minimizing the objective function





  
    
      
        Ψ
        =
        
        ⁢
        
          
            
            
              e
              
                (
                rec
                )
              
            
            
          
          2
        
      
    
  
  
    
      
        =
        
        ⁢
        
          〈
          
            
              F
              *
              
                (
                
                  e
                  -
                  α
                
                )
              
            
            ❘
            
              F
              *
              
                (
                
                  e
                  -
                  α
                
                )
              
            
          
          〉
        
      
    
  
  
    
      
        =
        
        ⁢
        
          〈
          
            
              
                L
                
                  (
                  rec
                  )
                
              
              ⁡
              
                (
                
                  e
                  -
                  α
                
                )
              
            
            ❘
            
              e
              -
              α
            
          
          〉
        
      
    
  




where L(rec)=FF*. The following sections 9-11 provide approximate solutions of the optimization problem.

6. Minimizing Error After Linear Operation

If the frame coefficients undergo a known linear operation, e.g., linear filtering, prior to frame synthesis, then the above formulation needs to be modified to accommodate this linear operation. Assume that a linear operator S: l2(Z)→l2(Z) is applied to the original frame coefficients c. The reconstructed signal has the general form:

x=F*S(c)

Therefore the earlier formulation of the optimization problem still applies and we get the optimization model:





  
    
      
        Ψ
        =
        
        ⁢
        
          〈
          
            
              F
              *
              
                S
                ⁡
                
                  (
                  
                    e
                    -
                    α
                  
                  )
                
              
            
            ❘
            
              F
              *
              
                S
                ⁡
                
                  (
                  
                    e
                    -
                    α
                  
                  )
                
              
            
          
          〉
        
      
    
  
  
    
      
        =
        
        ⁢
        
          〈
          
            
              
                L
                
                  (
                  linear
                  )
                
              
              ⁡
              
                (
                
                  e
                  -
                  α
                
                )
              
            
            ❘
            
              e
              -
              α
            
          
          〉
        
      
    
  




where

L(linear)=S*FF*S 

Where S* is the adjoint operator of S. Note that with the above formulation, we minimize the reconstruction error after the linear operator even though the quantization takes place before the linear operator.
7. Minimizing Quantization Error
The objective function for minimization of the quantization error in l2(Z) is:




  
    
      
        Ψ
        =
        
        ⁢
        
          
            
            
              
                Q
                error
              
              ⁡
              
                (
                c
                )
              
            
            
          
          2
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            
            
              γ
              +
              
                (
                
                  e
                  -
                  α
                
                )
              
            
            
          
          2
        
      
    
  




where γ=Σn γn v(n) is in ker(F*). For any value of a the value of γ that yields the minimization is equivalent to the projection of e−α onto ker(F*) in l2(Z); i.e.,

γj=−e−α|v(j)

Define the projection operation P: l2(Z) ker(F*) as

P(c)=Σjc|v(j)v(j) 

Then the objective function can be rewritten as:

Ψ∥(I−P)(e−α)∥2 

Note that I−P is the orthogonal projection operator onto ran(F); hence, it is a self-adjoint operator. Therefore, the optimization problem has the same form as the previous but with





  
    
      
        
          L
          
            (
            quant
            )
          
        
        =
        
        ⁢
        
          
            (
            
              I
              -
              P
            
            )
          
          2
        
      
    
  
  
    
      
        =
        
        ⁢
        
          (
          
            I
            -
            P
          
          )
        
      
    
  




Note that:

∥e(rec)∥=∥F*Qerror(c)∥≦∥F*∥∥Qerror(c)∥

where ∥F*∥ denotes the usual operator norm sup∥c∥=1∥F*(c)∥. Thus there is a direct proportion between the minimization of the quantization error and the minimization of the reconstruction error.

8. Optimization

The optimizations of preceding sections 5-7 all have the same form with an operator L which is a positive, self-adjoint operator in l2(Z). L is also a compact operator because it is the limit of a sequence of finite-rank approximation operators due to the frame definition upper bound; e.g., for L(rec) we have

L(rec)(c)k=ΣjεJ cj φj|φ

Next, define the finite rank approximation Ln as




  
    
      
        
          
            
              
                L
                n
              
              ⁡
              
                (
                c
                )
              
            
            k
          
          =
          
          ⁢
          
            
              
                〈
                
                  
                    
                      ∑
                      
                        j
                        ≤
                        n
                      
                      
                        
                      
                    
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        c
                        j
                      
                      ⁢
                      
                        φ
                        j
                      
                    
                  
                  ❘
                  
                    φ
                    k
                  
                
                〉
              
              ⁢
              
                
              
              ⁢
              if
              ⁢
              
                
              
              ⁢
              k
            
            ≤
            n
          
        
      
    
    
      
        
          =
          
          ⁢
          
            
              0
              ⁢
              
                
              
              ⁢
              if
              ⁢
              
                
              
              ⁢
              k
            
            >
            n
          
        
      
    
  




  Then




  
    
      
        
          
            
              (
              
                
                  L
                  
                    (
                    rec
                    )
                  
                
                -
                
                  L
                  n
                
              
              )
            
            ⁢
            
              
                (
                c
                )
              
              k
            
          
          =
          
          ⁢
          
            
              
                〈
                
                  
                    
                      ∑
                      
                        j
                        >
                        n
                      
                      
                        
                      
                    
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        c
                        j
                      
                      ⁢
                      
                        φ
                        j
                      
                    
                  
                  ❘
                  
                    φ
                    k
                  
                
                〉
              
              ⁢
              
                
              
              ⁢
              if
              ⁢
              
                
              
              ⁢
              k
            
            ≤
            n
          
        
      
    
    
      
        
          =
          
          ⁢
          
            
              
                
                  
                    L
                    
                      (
                      rec
                      )
                    
                  
                  ⁡
                  
                    (
                    c
                    )
                  
                
                k
              
              ⁢
              
                
              
              ⁢
              if
              ⁢
              
                
              
              ⁢
              k
            
            >
            n
          
        
      
    
  



The operator norm is:

∥(L(rec)−Ln)∥=sup∥c|=1∥(L(rec)−Ln)(c)∥

So squaring and using the frame definition:




  
    
      
        
          
            
              
              
                (
                
                  
                    L
                    
                      (
                      rec
                      )
                    
                  
                  -
                  
                    L
                    n
                  
                
                )
              
              
            
            2
          
          =
          
          ⁢
          
            
              sup
              
                
                  
                  c
                  
                
                =
                1
              
            
            ⁢
            
              
                
                
                  
                    (
                    
                      
                        L
                        
                          (
                          rec
                          )
                        
                      
                      -
                      
                        L
                        n
                      
                    
                    )
                  
                  ⁢
                  
                    (
                    c
                    )
                  
                
                
              
              2
            
          
        
      
    
    
      
        
          =
          
          ⁢
          
            
              sup
              
                
                  
                  c
                  
                
                =
                1
              
            
            ⁢
            
              
                ∑
                
                  i
                  ,
                  
                    j
                    >
                    n
                  
                
                
                  
                
              
              ⁢
              
                
              
              ⁢
              
                
                  
                  
                    
                      c
                      j
                    
                    ⁢
                    
                      〈
                      
                        
                          φ
                          i
                        
                        ❘
                        
                          φ
                          j
                        
                      
                      〉
                    
                  
                  
                
                2
              
            
          
        
      
    
    
      
        
          
          ⁢
          
            <
            
              
                A
                2
              
              ⁢
              max
              ⁢
              
                
              
              ⁢
              
                (
                
                  
                    
                    
                      φ
                      j
                    
                    
                  
                  2
                
                )
              
              ⁢
              
                
                  ∑
                  
                    i
                    >
                    n
                  
                  
                    
                  
                
                ⁢
                
                  
                
                ⁢
                
                  
                    
                    
                      c
                      i
                    
                    
                  
                  2
                
              
            
          
        
      
    
  




  And




  
    
      
        ∑
        
          i
          >
          n
        
        
          
        
      
      ⁢
      
        
      
      ⁢
      
        
          
          
            c
            i
          
          
        
        2
      
    
    →
    0.
  



The unknown variable (i.e., quantization method) is the integer vector α. The objective function for reconstruction error minimization can be put into an alternate form (after removing the irrelevant term Le|e):

Ψ(rec)=L(rec)α|α—2 Re{L(rec)α|e}

Note that the reconstruction mean squared error (MSE) of the rounding solution does not improve with increased redundancy after a linear operator. This is primarily because a general linear operator moves components of the kernel of the quantization error into the domain of the synthesis operator. This situation is avoided in the formulation of the optimization problem with the operator L(linear) to get consistent improvement.

Since each of the operators L is a compact, positive, self-adjoint operator, it has positive real eigenvalues and the eigenvectors that correspond to distinct eigenvalues are orthogonal. Moreover, the space spanned by the eigenvectors represents the domain of L, (i.e., the orthogonal space is ker(L)). Let {wj} be an orthonormal basis of the eigenvectors of L so that L wj=λj wj where λj is real and positive. Let ηj=α|wj and ζj=e|wj; then the objective function becomes:




  
    
      
        
          Ψ
          
            (
            rec
            )
          
        
        =
        
        ⁢
        
          
            〈
            
              
                
                  ∑
                  j
                  
                    
                  
                
                ⁢
                
                  
                
                ⁢
                
                  
                    λ
                    j
                  
                  ⁢
                  
                    η
                    j
                  
                  ⁢
                  
                    w
                    j
                  
                
              
              ❘
              α
            
            〉
          
          -
          
            2
            ⁢
            
              
            
            ⁢
            Re
            ⁢
            
              {
              
                〈
                
                  
                    
                      ∑
                      j
                      
                        
                      
                    
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        λ
                        j
                      
                      ⁢
                      
                        η
                        j
                      
                      ⁢
                      
                        w
                        j
                      
                    
                  
                  ❘
                  e
                
                〉
              
              }
            
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            ∑
            j
            
              
            
          
          ⁢
          
            
          
          ⁢
          
            
              λ
              j
            
            ⁡
            
              (
              
                
                  
                    
                    
                      η
                      j
                    
                    
                  
                  2
                
                -
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  Re
                  ⁢
                  
                    {
                    
                      
                        η
                        j
                      
                      ⁢
                      
                        ζ
                        j
                        *
                      
                    
                    }
                  
                
              
              )
            
          
        
      
    
  




In the finite dimensional case a positive self-adjoint operator can be represented by a positive semidefinite matrix. The optimization problem in this case is reduced to a standard constrained quadratic integer programming problem (with the constraint that the last element of any feasible solution is one). For infinite dimensional frames we still have the same model but with infinite number of variables. However, we add the constraint that any feasible solution should be in l2(Z). Therefore we assume that there exists a positive integer N such that αj=0 for j>N.
The optimal solution of the above optimization problem can be computed directly using enumeration for small frame size. For moderate sizes, (e.g., less than 100), the problem can be transformed into a semidefinite programming problem to find a suboptimal solution. However, as size grows it can only be solved using numerical search techniques, e.g., Tabu search. In the following section we describe an efficient heuristic that exploits the optimization model for the overcomplete frames to significantly prune the search space.
9. Approximation
The search procedure described in this section is a reformulation of the objective function for reconstruction error. In particular, we describe a search technique that minimizes the correlation between successive incremental vectors by exploiting the frame redundancy. Since the operator L is a positive self-adjoint operator, it can be written as L=B2 where B is a bounded self-adjoint operator. Let {uj} be the elementary orthonormal basis of l2(Z), i.e., δi, j. Also, define:

eR=B(e)

bj=B(uj)

Then using L=B2=B*B, the objective function can be written as:





  
    
      
        
          Ψ
          
            (
            rec
            )
          
        
        =
        
        ⁢
        
          
            
            
              e
              
                (
                rec
                )
              
            
            
          
          2
        
      
    
  
  
    
      
        =
        
        ⁢
        
          〈
          
            
              L
              ⁡
              
                (
                
                  e
                  -
                  α
                
                )
              
            
            ❘
            
              e
              -
              α
            
          
          〉
        
      
    
  
  
    
      
        =
        
        ⁢
        
          〈
          
            
              B
              ⁡
              
                (
                
                  e
                  -
                  α
                
                )
              
            
            ❘
            
              B
              ⁡
              
                (
                
                  e
                  -
                  α
                
                )
              
            
          
          〉
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            
            
              
                B
                ⁡
                
                  (
                  e
                  )
                
              
              -
              
                B
                ⁡
                
                  (
                  α
                  )
                
              
            
            
          
          2
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            
            
              
                e
                R
              
              -
              
                
                  ∑
                  
                    j
                    ∈
                    J
                  
                  
                    
                  
                
                ⁢
                
                  
                
                ⁢
                
                  
                    α
                    j
                  
                  ⁢
                  
                    b
                    j
                  
                
              
            
            
          
          2
        
      
    
  




For overcomplete frames, the set of vectors {bj} are linearly dependent. This redundancy can be exploited to prune the search space of the optimization problem. This is a clustering problem that is discussed in details in the following sections.

10. Clustering Procedure

The objective of the clustering procedure is to cluster the possibly infinite set {bj} from the preceding section to at most M clusters such that the mutual correlations between clusters are minimized. Moreover, each cluster is to have two representatives: one is a vector in l2(Z) that is used in testing the search increments and the second is a binary vector for elements of a.
In particular, given a set of vectors {bj}, the preferred embodiment methods generate M clusters with minimal mutual correlation between clusters. Note that in practice we have the original unquantized sequence c in l2(Z); hence cj→0; i.e., for each ε>0, there exists N(ε) such that |cj|<ε for j>N(ε), which is also dependent upon c. If we choose c to be much smaller than a single quantization step, we may assume that αj=0 for j>N(ε). Therefore, we have N vectors and are required to generate M clusters. The solution space of the optimization problem has 2N possible binary solutions a. Each cluster corresponds to a search increment in the quantization phase. The preferred embodiment clustering procedure is to minimize the correlations between successive search increments by reducing the overall correlation between clusters. The clustering procedure proceeds as follows:
1) Generate clusters in multiples of S≦N; i.e., we generate S clusters at each iteration.
2) The initial centers of the S clusters at each iteration are an orthonormal basis for l2(Z) denoted {gj}.
3) The first vector bj that is classified to the k-th cluster is the vector that maximizes the normalized correlation |gk|bj|/∥bj∥. The cluster vector representative becomes bj and the binary representative has 1 only in the j-th location and 0 elsewhere. Denote the cluster representative by hk; i.e., initially hk=bj.
4) For each other vector bi, include it in the k-th cluster when

|gk|bi±hk|/∥bi±hk∥<|gk|hk|/∥hk∥.

In this case the cluster representative is updated to bi±hk and the i-th location in the binary representative vector is updated to 1 with the proper sign.

5) The set of S initial orthonormal vectors {gj} can be generated using Gram-Schmidt procedure on {bj} with different vector order, or by rotating the eigenvectors of the linear operator by a fixed angle using a rotation operator.
Note that the complexity of the clustering procedure is not a critical issue sin ce it is performed offline.
In the finite dimensional case, e.g., RN, the linear operator is approximated by a positive semidefinite matrix Γ, which in general can be expressed as Γ=B2, where B is a hermitian matrix that can be directly computed using a unitary transformation of the Cholesky decomposition of Γ. In this case the vectors {bj} are simply the columns of B. The number of nonzero vectors equals rank (B) and this equals the maximum number of clusters within a group.
11. Quantization Procedure
At the end of clustering procedure, we have M clusters each with one representative vector {hj} j=1, 2, . . . , M and one binary vector for the increment {μj} j=1, 2, . . . , M. The quantization search proceeds as follows:

    1) compute eR as B(e), and set α=0.
    2) for j=1,2, . . . M, if ∥eR±hj∥<∥eR∥, then replace eR with eR±hj, and update binary vector α to α±μj.
    3) Step 2 is repeated as needed or until convergence.

Note that the comparison in step 2) can be simplified to:

|eR|h|<(1⁄2)∥hj∥2 

The total computation overhead for the preferred embodiment is as follows:

    1) Linear operator computation for computing eR as B(e).
    2) M inner product operations for the search |eR|hj|<(1⁄2)∥hj∥2.


In summary, the preferred embodiment methods include the steps of:

    
    
        (a) given a frame {φn}, compute (offline) the bj=B(u);
        (b) cluster (offline) the bj into M clusters with cluster vectors hk and increment vectors μk.
        (c) compute frame expansion coefficients cj for an input signal (i.e., oversampling); the input signal typically would be partitioned into overlapping blocks so the computation is finite and limited delay;
        (d) quantize the cj by the following steps (i) to (iii):
        
            (i) compute ej=cj−└cj┘ and eR=B(e);
            (ii) for j=1, 2, . . . , M: when ∥eR±hj∥<∥eR∥, update eR to eR±hj and α to α≠μj; (α was initialized as the 0 vector); this cycling through the clusters is repeated until convergence (i.e., no more updates).
            (iii) quantize cj as └cj┘+αj.

FIG. 1B heuristically illustrates the preferred embodiments: the input analog signal x and two reconstructed analog signals x(rec1) and x(rec2) in H are shown in the lower portion, and the oversampled F(x) plus two possible quantizations in l2(Z) are shown in the upper portion. The preferred embodiments find the quantization to minimize reconstruction error.

12. Additional

        
        
    
    


Section 11 described a search technique that is based on minimizing the correlation between successive moves. Unlike the problem of classical integer programming problem where we deal with binary vectors that do not reveal much information, the preferred embodiment uses a clustering technique to work with meaningful vectors to the optimization problem that are the representative for each cluster.
In the case where the delay is a concern (especially in the infinite dimensional case) the clusters can be designed such that the representative binary vector of each cluster is zero outside the allowable delay. Also, the error in a group of S clusters can be reduced by correcting for the additional errors in the following groups of clusters in a procedure that could be considered a generalization of the projection procedure onto the next frame sample that was described in Boufounos and Oppenheim, cited in the background.
As an infinite-dimensional example, consider I(rec)=FF* of section 5 with T=1 for notational simplicity; then φn(t)=(1/r)sin c(t−n/r) is the synthesis frame and φdual, n(t)=sin c(t−n/r) is the analysis frame. Compute B as follows. First, L(rec)(uj)k=FF*(uj)k=F(φj(t))k=φdual, k(t)|φj(t)=(1/r)sin c(k/r−j/r). Next, presume B is translation invariant like L:

B(c)k=ΣnεZ βk-n cn 

Then, L(rec)(uj)k=BB(uj)k implies

(1/r)sin c(k/r−j/r)=ΣnεZ βk-n βn-j 

or with a variable change:

(1/r)sin c(m/r)=ΣnεZ βm-n βn 

Next, Fourier transform l2(Z)→L2(−1⁄2, 1⁄2) to convert the convolution into a multiplication. Then note the Fourier transform of (1/r)sin c(n/r) is rect(rθ) to have

βn=(1/r)sin c(n/r)

So the vectors for the cluster computations are:





  
    
      
        
          
            b
            j
          
          ⁡
          
            (
            k
            )
          
        
        =
        
        ⁢
        
          
            B
            ⁡
            
              (
              
                u
                j
              
              )
            
          
          k
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            (
            
              1
              /
              r
            
            )
          
          ⁢
          
            sinc
            ⁡
            
              (
              
                
                  k
                  /
                  r
                
                -
                
                  j
                  /
                  r
                
              
              )
            
          
        
      
    
  




Then bm|bn=Σkεz(1/r)sin c(m/r−k/r)(1/r)sin c(n/r−k/r)=(1/r)sin c(m/r−n/r), so ∥bj∥2=1/r. Intuitively, the oversampling scales down the vector components by a factor of (1/r) to compensate for the redundancy factor r in the expansion; and heuristically the (infinite) dimension of ran(F) is 1/r of the total dimension, so for a random vector the projection onto ran(F) decreases the norm by a factor of 1/√r.

The orthonormal basis {gj} could then be taken as gj=(√r)bjr. Then the first vector in the k-th cluster would be bkr and thus be the initial hk.
For the k-th cluster, vector bi is included when:

|gk|bi±hk|/∥bi±hk∥>|gk|hk|/∥hk∥.

Squaring both sides, cross multiplying, and dividing out the square root of r normalization converts the condition into:

|bkr|bi±bkr|2∥bkr∥2>|bkr|bkr|2∥bi±bkr∥2.

Divide out ∥bkr∥2=|bkr|bkr2 The left side then equals:





  
    
      
        
          
            
            
              〈
              
                
                  b
                  kr
                
                ❘
                
                  
                    b
                    i
                  
                  ±
                  
                    b
                    kr
                  
                
              
              〉
            
            
          
          2
        
        =
        
        ⁢
        
          
            
            
              
                〈
                
                  
                    b
                    kr
                  
                  ❘
                  
                    b
                    i
                  
                
                〉
              
              ±
              
                〈
                
                  
                    b
                    kr
                  
                  ❘
                  
                    b
                    kr
                  
                
                〉
              
            
            
          
          2
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            (
            
              1
              /
              
                r
                2
              
            
            )
          
          ⁢
          
            
              
              
                
                  sinc
                  ⁡
                  
                    (
                    
                      
                        kr
                        /
                        r
                      
                      -
                      
                        i
                        /
                        r
                      
                    
                    )
                  
                
                ±
                1
              
              
            
            2
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            (
            
              1
              /
              
                r
                2
              
            
            )
          
          ⁢
          
            ⌈
            
              
                
                  
                    sinc
                    ⁡
                    
                      (
                      
                        
                          kr
                          /
                          r
                        
                        -
                        
                          i
                          /
                          r
                        
                      
                      )
                    
                  
                  2
                
                ±
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  
                    sinc
                    ⁡
                    
                      (
                      
                        
                          kr
                          /
                          r
                        
                        -
                        
                          i
                          /
                          r
                        
                      
                      )
                    
                  
                
              
              +
              1
            
            ⌉
          
        
      
    
  




The right side equals





  
    
      
        
          
            
            
              
                b
                i
              
              ±
              
                b
                kr
              
            
            
          
          2
        
        =
        
        ⁢
        
          
            
              
                
                
                  b
                  i
                
                
              
              2
            
            ±
            
              2
              ⁢
              
                〈
                
                  
                    b
                    i
                  
                  ❘
                  
                    b
                    kr
                  
                
                〉
              
            
          
          +
          
            
              
              
                b
                kr
              
              
            
            2
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            (
            
              1
              /
              
                r
                2
              
            
            )
          
          ⁡
          
            [
            
              
                1
                ±
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  
                    sinc
                    ⁡
                    
                      (
                      
                        
                          kr
                          /
                          r
                        
                        -
                        
                          i
                          /
                          r
                        
                      
                      )
                    
                  
                
              
              +
              1
            
            ]
          
        
      
    
  




The left side is always smaller because sin c(kr/r−i/r)2<1; thus the clusters have a single representative, and the quantization search is simply over the vectors corresponding to samples of lowpass-filtered pulses at the Nyquist rate.

13. Experimental Results

In our simulation we use a finite dimensional Hilbert space generated by the Fourier series coefficients of periodic band-limited functions as in Goyal et al., Quantized Overcomplete Expansions in RN: Analysis, Synthesis, and Algorithms, 44 IEEE Tran. Info Theory 16 (January 1998). In particular, a real-valued function x(t) with period T, integrable over [0, T], and with maximum frequency W can be expanded in a finite Fourier series:

x(t)=X(1)+Σ1≦k≦WX(2k)√2 cos [2πkt/T]+X(2k+1)√2 sin [2πkt/T]

Thus take the Hilbert space H as RN where N=2W+1 and the function x(t) is represented by the vector





  [
  
    
      
        
          X
          ⁡
          
            (
            1
            )
          
        
      
    
    
      
        
          X
          ⁡
          
            (
            2
            )
          
        
      
    
    
      
        
          X
          ⁡
          
            (
            3
            )
          
        
      
    
    
      
        ...
      
    
    
      
        
          X
          ⁡
          
            (
            N
            )
          
        
      
    
  
  ]




in H. Now samples of x(t) at M equi-spaced points in [0, T] can be written as:

x(mT/M)=X(1)+Σ1≦k≦WX(2k)√2 cos [2πkm/M]+X(2k+1)√2 sin [2πkm/M]

where m=0, 1, 2, . . . , M−1 (or equivalently by periodicity, m=1, 2, . . . , M). Denote these samples as a vector c in RM (which replaces l2(Z) in this finite-dimensional case) with components cm=x(mT/M). Oversampling corresponds to M>N. And the samples can be written as inner products in H:




  
    
      c
      m
    
    =
    
      〈
      
        X
        ❘
        
          φ
          m
        
      
      〉
    
  




  where




  
    
      φ
      m
    
    =
    
      [
      
        
          
            1
          
        
        
          
            
              
                2
              
              ⁢
              
                cos
                ⁡
                
                  [
                  
                    2
                    ⁢
                    
                      
                    
                    ⁢
                    π
                    ⁢
                    
                      
                    
                    ⁢
                    
                      m
                      /
                      M
                    
                  
                  ]
                
              
            
          
        
        
          
            
              
                2
              
              ⁢
              
                sin
                ⁡
                
                  [
                  
                    2
                    ⁢
                    
                      
                    
                    ⁢
                    π
                    ⁢
                    
                      
                    
                    ⁢
                    
                      m
                      /
                      M
                    
                  
                  ]
                
              
            
          
        
        
          
            ...
          
        
        
          
            
              
                2
              
              ⁢
              
                sin
                ⁡
                
                  [
                  
                    2
                    ⁢
                    
                      
                    
                    ⁢
                    π
                    ⁢
                    
                      
                    
                    ⁢
                    
                      Wm
                      /
                      M
                    
                  
                  ]
                
              
            
          
        
      
      ]
    
  



The {φm} form the frame in H, and then the frame analysis operator F: H→RM maps X→c where cm=X|φm. Thus F corresponds to the M×N matrix with elements Fm, 1=1, Fm, 2k=√2 cos [2πkm/M], and Fm, 2k+1=√2 sin [2πkm/M]; that is, the m-th row of F is φm. The frame synthesis operator F* : RM→H maps c→Y where

Y(1)=Σ1≦m≦M cm,

Y(2k)=Σ1≦m≦M cm √2 cos [2πkm/M], 

Y(2k+1)=Σ1≦m≦M cm √2 sin [2πkm/M], 

F* corresponds to the N×M matrix which is the adjoint of the F matrix so the columns of F* are the {φm}, and F*F=M I33 N. Further, the optimization operator L=FF*: RM→RM corresponds to the M×M matrix with elements φn|φm. Note that





  
    〈
    
      
        φ
        n
      
      ❘
      
        φ
        m
      
    
    〉
  
  =
  
    1
    +
    
      2
      ⁢
      
        (
        
          
            
              cos
              ⁡
              
                [
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  π
                  ⁢
                  
                    
                  
                  ⁢
                  
                    m
                    /
                    M
                  
                
                ]
              
            
            ⁢
            
              cos
              ⁡
              
                [
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  π
                  ⁢
                  
                    
                  
                  ⁢
                  
                    n
                    /
                    M
                  
                
                ]
              
            
          
          +
          
            
              sin
              ⁡
              
                [
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  π
                  ⁢
                  
                    
                  
                  ⁢
                  
                    m
                    /
                    M
                  
                
                ]
              
            
            ⁢
            
              sin
              ⁡
              
                [
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  π
                  ⁢
                  
                    
                  
                  ⁢
                  
                    n
                    /
                    M
                  
                
                ]
              
            
          
        
        )
      
    
    +
    
      2
      ⁢
      
        (
        
          
            
              cos
              ⁡
              
                [
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  π
                  ⁢
                  
                    
                  
                  ⁢
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  
                    m
                    /
                    M
                  
                
                ]
              
            
            ⁢
            
              cos
              ⁡
              
                [
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  π
                  ⁢
                  
                    
                  
                  ⁢
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  
                    n
                    /
                    M
                  
                
                ]
              
            
          
          +
          
            
              sin
              ⁡
              
                [
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  π
                  ⁢
                  
                    
                  
                  ⁢
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  
                    m
                    /
                    M
                  
                
                ]
              
            
            ⁢
            
              sin
              ⁡
              
                [
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  π
                  ⁢
                  
                    
                  
                  ⁢
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  
                    n
                    /
                    M
                  
                
                ]
              
            
          
        
        )
      
    
    +
    ...
    +
    
      2
      ⁢
      
        (
        
          
            
              cos
              ⁡
              
                [
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  π
                  ⁢
                  
                    
                  
                  ⁢
                  
                    km
                    /
                    M
                  
                
                ]
              
            
            ⁢
            
              cos
              ⁡
              
                [
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  π
                  ⁢
                  
                    
                  
                  ⁢
                  
                    kn
                    /
                    M
                  
                
                ]
              
            
          
          +
          
            
              sin
              ⁡
              
                [
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  π
                  ⁢
                  
                    
                  
                  ⁢
                  
                    km
                    /
                    M
                  
                
                ]
              
            
            ⁢
            
              sin
              ⁡
              
                [
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  π
                  ⁢
                  
                    
                  
                  ⁢
                  
                    kn
                    /
                    M
                  
                
                ]
              
            
          
        
        )
      
    
    +
    ...
    +
    
      2
      ⁢
      
        (
        
          
            
              cos
              ⁡
              
                [
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  π
                  ⁢
                  
                    
                  
                  ⁢
                  
                    Wm
                    /
                    M
                  
                
                ]
              
            
            ⁢
            
              cos
              ⁡
              
                [
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  π
                  ⁢
                  
                    
                  
                  ⁢
                  
                    Wn
                    /
                    M
                  
                
                ]
              
            
          
          +
          
            
              sin
              ⁡
              
                [
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  π
                  ⁢
                  
                    
                  
                  ⁢
                  
                    Wm
                    /
                    M
                  
                
                ]
              
            
            ⁢
            
              sin
              ⁡
              
                [
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  π
                  ⁢
                  
                    
                  
                  ⁢
                  
                    Wn
                    /
                    M
                  
                
                ]
              
            
          
        
        )
      
    
  




Then using the cosine addition formula:





  
    
      
        
          〈
          
            
              φ
              n
            
            ❘
            
              φ
              m
            
          
          〉
        
        =
        
        ⁢
        
          1
          +
          
            2
            ⁢
            
              
            
            ⁢
            
              cos
              ⁡
              
                [
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      π
                      ⁡
                      
                        (
                        
                          m
                          -
                          n
                        
                        )
                      
                    
                    /
                    M
                  
                
                ]
              
            
          
          +
        
      
    
  
  
    
      
        
        ⁢
        
          
            2
            ⁢
            
              
            
            ⁢
            
              cos
              ⁡
              
                [
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  π
                  ⁢
                  
                    
                  
                  ⁢
                  2
                  ⁢
                  
                    
                      (
                      
                        m
                        -
                        n
                      
                      )
                    
                    /
                    M
                  
                
                ]
              
            
          
          +
          ...
          +
        
      
    
  
  
    
      
        
        ⁢
        
          
            2
            ⁢
            
              
            
            ⁢
            
              cos
              ⁡
              
                [
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  π
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      k
                      ⁡
                      
                        (
                        
                          m
                          -
                          n
                        
                        )
                      
                    
                    /
                    M
                  
                
                ]
              
            
          
          +
          ...
          +
        
      
    
  
  
    
      
        
        ⁢
        
          2
          ⁢
          
            
          
          ⁢
          
            cos
            ⁡
            
              [
              
                2
                ⁢
                
                  
                
                ⁢
                π
                ⁢
                
                  
                
                ⁢
                
                  
                    W
                    ⁡
                    
                      (
                      
                        m
                        -
                        n
                      
                      )
                    
                  
                  /
                  M
                
              
              ]
            
          
        
      
    
  
  
    
      
        
          =
          
          ⁢
          
            
              sin
              ⁡
              
                [
                
                  2
                  ⁢
                  
                    π
                    ⁡
                    
                      (
                      
                        W
                        +
                        
                          1
                          ⁢
                          
                            /
                          
                          ⁢
                          2
                        
                      
                      )
                    
                  
                  ⁢
                  
                    
                      (
                      
                        m
                        -
                        n
                      
                      )
                    
                    /
                    M
                  
                
                ]
              
            
            /
            
              sin
              ⁡
              
                [
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  
                    π
                    ⁡
                    
                      (
                      
                        1
                        ⁢
                        
                          /
                        
                        ⁢
                        2
                      
                      )
                    
                  
                  ⁢
                  
                    
                      (
                      
                        m
                        -
                        n
                      
                      )
                    
                    /
                    M
                  
                
                ]
              
            
          
        
        ⁢
        
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            sin
            ⁡
            
              [
              
                π
                ⁢
                
                  
                
                ⁢
                
                  
                    N
                    ⁡
                    
                      (
                      
                        m
                        -
                        n
                      
                      )
                    
                  
                  /
                  M
                
              
              ]
            
          
          /
          
            sin
            ⁡
            
              [
              
                
                  π
                  ⁡
                  
                    (
                    
                      m
                      -
                      n
                    
                    )
                  
                
                /
                M
              
              ]
            
          
        
      
    
  




The test vectors in RN are Gaussian independent, identically-distributed sequences with unity variance. The frame functions {φm} in the synthesis process are not quantized. In the first experiment, we establish the effectiveness of the preferred embodiment search method as described in section 11. We fix N=4, and increase the redundancy factor r. We set the number of reduced search vectors in RN to M=N×r (compared to the total search space of 2M). The M search vectors are generated as described in section 10. In a single iteration we have M search steps as described in section 11. To evaluate the preferred embodiment method, we simulate the results of Boufounos and Oppenheim (cited in the background) for frame quantization by projecting the quantization error onto the following frame coefficient. The results are shown in FIG. 2A.
The preferred embodiment search method gives significant improvement in the reconstruction mean square error (MSE) over the rounding solution. Note that the rounding solution has an error behavior almost O(1/r) which is proportional to the dimension of ker(F*). The preferred embodiment search method with the described parameters performs better than the projection algorithm in Boufounos and Oppenheim which simulates the sigma-delta quantization for redundant frames, therefore, the SNR is O(1/r3) as it resembles the error behavior of a single stage sigma-delta converter. On the other hand, the error behavior of the preferred embodiment is approximately O(1/r4) which is a significant improvement. This performance is typical for any frame order. One other important point from the figure is that most of the improvement occurs in the first iteration. This is due to the efficient procedure for constructing the search movements with orthogonal sets. Note that, the described order of iterations of the preferred embodiment search method is several orders of magnitude less than typical search algorithms for integer programming problems.
Next we test the performance when the frame coefficients undergo a linear operation. In particular, we multiply the frame coefficients in RM by an M×M matrix with uniformly distributed entries. We use the optimization model described in section 6. The results are illustrated and compared with the rounding solution in FIG. 2B which has similar behavior to the first experiment.
Note that the reconstruction MSE of the rounding solution does not improve with increased redundancy after a linear operator. This is primarily because a general linear operator moves kernel components of the quantization error to the domain of the synthesis operator. This situation is avoided in the formulation of the optimization problem in section 6 to get the consistent improvement.

## Claims

1. A quantization method for enhancing an image, comprising:
(a) providing a vector c of frame expansion coefficients cj for an input signal, where the cj are expressed as multiples of a quantization step size;
(b) computing a vector of truncation errors e where for each coefficient ej =cj−floor(cj), where floor(cj) denotes the integer part of cj;
(c) computing eR =B(e), where B is a projection onto a subspace of vectors of possible expansion coefficients;
(d) initializing a binary vector α as the 0 vector and provide M clusters of vectors in said subspace where said clusters are of correlated vectors and a j-th cluster has representative vector hj and binary increment vector μj;
(d) for j =1, 2, . . . , M: when ∥eR±hj∥<∥eR∥, updating eR to eR±hj and update α to α±μj;
(e) repeating step (d) until there are no more updates; and
(f) outputting for each coefficient cj the sum floor(cj) +αj;
(g) utilizing the outputted sum floor(cj) +αj for each coefficient cj in quantization, wherein said quantization produces an enhanced image.

2. The method of claim 1, wherein the method is utilized for oversampled signals with an error minimization searches.