# Patent

## Title
Alternating direction of multipliers method for parallel MRI reconstruction

## Abstract

A method for reconstructing parallel magnetic resonance images includes providing a set of acquired k-space MR image data y, and finding a target MR image x that minimizes 1⁄2∥Fv−y∥22+λ∥z∥1 where v=Sx and z=Wx where S is a diagonal matrix containing sensitivity maps of coil elements in an MR receiver array, F is an FFT matrix, W is a redundant Haar wavelet matrix, and λ≧0 is a regularization parameter, by updating



  
    
      
        x
        
          k
          +
          1
        
      
      =
      
        
          
            (
            
              
                
                  μ
                  1
                
                ⁢
                I
              
              +
              
                
                  μ
                  3
                
                ⁢
                
                  S
                  H
                
                ⁢
                S
              
            
            )
          
          
            -
            1
          
        
        ⁡
        
          [
          
            
              
                μ
                1
              
              ⁢
              
                
                  W
                  H
                
                ⁡
                
                  (
                  
                    
                      z
                      k
                    
                    -
                    
                      b
                      z
                      k
                    
                  
                  )
                
              
            
            +
            
              
                μ
                3
              
              ⁢
              
                
                  S
                  H
                
                ⁡
                
                  (
                  
                    
                      v
                      k
                    
                    -
                    
                      b
                      v
                      k
                    
                  
                  )
                
              
            
          
          ]
        
      
    
    ,
    
      

    
    ⁢
    
      
        z
        
          k
          +
          1
        
      
      =
      
        
          soft
          ⁡
          
            (
            
              
                
                  Wx
                  
                    k
                    +
                    1
                  
                
                +
                
                  b
                  z
                  k
                
              
              ,
              
                1
                
                  μ
                  1
                
              
            
            )
          
        
        ⁢
        
          
        
        ⁢
        where
      
    
  




  
    
      soft
      ⁡
      
        (
        
          x
          ,
          T
        
        )
      
    
    =
    
      {
      
        
          
            
              
                
                  
                    x
                    +
                    T
                  
                
                
                  
                    
                      
                        if
                        ⁢
                        
                          
                        
                        ⁢
                        x
                      
                      ≤
                      
                        -
                        T
                      
                    
                    ,
                  
                
              
              
                
                  0
                
                
                  
                    
                      
                        if
                        ⁢
                        
                          
                        
                        ⁢
                        
                          
                          x
                          
                        
                      
                      ≤
                      T
                    
                    ,
                  
                
              
              
                
                  
                    x
                    -
                    T
                  
                
                
                  
                    
                      
                        if
                        ⁢
                        
                          
                        
                        ⁢
                        x
                      
                      ≥
                      T
                    
                    ,
                  
                
              
            
            ⁢
            
              

            
            ⁢
            and
            ⁢
            
              

            
            ⁢
            
              v
              
                k
                +
                1
              
            
          
          =
          
            
              
                (
                
                  
                    
                      F
                      H
                    
                    ⁢
                    F
                  
                  +
                  
                    
                      μ
                      3
                    
                    ⁢
                    I
                  
                
                )
              
              
                -
                1
              
            
            ⁡
            
              [
              
                
                  
                    F
                    H
                  
                  ⁢
                  y
                
                +
                
                  
                    μ
                    3
                  
                  ⁡
                  
                    (
                    
                      
                        Sx
                        
                          k
                          +
                          1
                        
                      
                      +
                      
                        b
                        v
                        k
                      
                    
                    )
                  
                
              
              ]
            
          
        
        ,
      
    
  



where k is an iteration counter, μ1 and μ3 are parameters of an augmented Lagrangian function, and bz and bv are dual variables of the augmented Lagrangian.

## Background
CROSS REFERENCE TO RELATED UNITED STATES APPLICATIONS
This application claims priority from “ADMM for Parallel MRI Reconstruction”, U.S. Provisional Application No. 61/616,545 of Liu, et al., filed Mar. 28, 2012, and the contents of which are herein incorporated by reference in their entireties.


TECHNICAL FIELD
This disclosure is directed to methods for parallel reconstruction of digital images.
DISCUSSION OF THE RELATED ART
Magnetic resonance imaging (MRI) is a medical imaging technique used in radiology to visualize internal structures of the body in detail. As a non-invasive imaging technique, MRI makes use of nuclear magnetic resonance to image nuclei of atoms inside the body. MRI has been used for imaging the brain, muscles, the heart, cancers, etc.
The raw data acquired by an MR scanner are the Fourier coefficients, or the so-called k-space data. The k-space data are typically acquired by a series of phase encodings, in which each phase encoding includes a given amount of k-space data that are related to the sampling. For example, with Cartesian sampling, 256 frequency encodings are needed to cover the full k-space of one 256×256 image. The time between the repetitions of the sequence is called the repetition time (TR) and is a measure of the time needed for acquiring one phase encoding. For example, if TR=50 ms, it takes about 12.8 seconds to acquire a full k-space data of one 256×256 image with Cartesian sampling. With the same TR, it takes about 15.4 minutes to acquire the full k-space of a 256×256×72 volume. With higher spatial resolution, the time for acquiring a full k-space increases. To reduce the acquisition time, one may undersample the k-space, i.e., reduce the number of acquired phase encodings.
Parallel imaging has been proven effective for reducing acquisition time. Parallel imaging exploits differences in sensitivities between individual coil elements in a receiver array to reduce the number of gradient encodings required for imaging. Parallel imaging tries to reconstruct the target image with the undersampled k-space data.
In parallel MRI, one is provide with the k-space observations from c coils as

yi=FuSix,  (1)

where x is the target MR image to be reconstructed, Si is a diagonal matrix containing the coil sensitivity map of the ith-coil, and Fu is a partial FFT matrix. Assuming a Cartesian sampling pattern, one has FuFuH=I.

Denoting the measurement matrix as

A=FS  (2)

where

F=diag(Fμ,1,Fμ,2, . . . ,Fμ,c)  (3)

is the complete FFT matrix, and

S=[S2,S2, . . . ,Sc]H,  (4)

composes the coil sensitivity estimations of all the c coils. The coil sensitivity maps may be normalized so that SHS=I, where the ‘H’ denotes a Hermitian adjoint matrix.

The relationship between the image x and the k-space observations y=[y1,y2, . . . ,yc] can be represented as

y=Ax.  (5)

Sparsity has been employed as a prior for parallel MRI reconstruction. Making use of the l1 regularization of the redundant Haar wavelets, one can estimate x by solving the following 2 formulations.
An unconstrained formulation computes x by optimizing




  
    
      
        
          
            
              min
              x
            
            ⁢
            
              
                1
                2
              
              ⁢
              
                
                  
                  
                    Ax
                    -
                    y
                  
                  
                
                2
                2
              
            
          
          +
          
            λ
            ⁢
            
              
                
                Wx
                
              
              1
            
          
        
        ,
      
    
    
      
        (
        6
        )
      
    
  




where W represents the redundant Haar wavelets, and λ is a parameter that trades data fidelity with the l1 regularization. Note that, although W is not invertible, WHW=I.

A constrained formulation computes x by optimizing




  
    
      
        
          min
          
            x
            :
            
              
                
                  
                  
                    Ax
                    -
                    y
                  
                  
                
                2
              
              ≤
              ɛ
            
          
        
        ⁢
        
          
            
            Wx
            
          
          1
        
      
    
    
      
        (
        7
        )
      
    
  




where ε represents the allowed discrepancy between the prediction and the observed k-space data.

SUMMARY
Exemplary embodiments of the invention as described herein generally include methods for alternating direction of multipliers (ADMM) for parallel MRI reconstruction by the l1 regularization of redundant Haar wavelets. Embodiments of the invention split both the data fidelity term and the non-smooth regularization term for an efficient, closed form update of the associated variables. In addition, embodiments of the invention introduce as few auxiliary variables as possible to save computation and storage cost. Embodiments of the invention set the ADMM parameters in a data dependent way to ensure fast convergence.
According to an embodiment of the invention, there is provided a method for reconstructing parallel magnetic resonance images (MRI), including providing a set of acquired k-space MR image data y, and finding a target MR image x that minimizes 1⁄2∥Fv−y∥22+λ∥z∥1 where v=Sx and z=Wx where S is a diagonal matrix containing sensitivity maps of coil elements in an MR receiver array, F is an FFT matrix where FFH=I and H denotes a Hermitian adjoint matrix, W is a redundant Haar wavelet matrix satisfying WTW=I, where I is an identity matrix, and λ≧0 is a regularization parameter, by updating



  
    
      
        x
        
          k
          +
          1
        
      
      =
      
        
          
            (
            
              
                
                  μ
                  1
                
                ⁢
                I
              
              +
              
                
                  μ
                  3
                
                ⁢
                
                  S
                  H
                
                ⁢
                S
              
            
            )
          
          
            -
            1
          
        
        ⁡
        
          [
          
            
              
                μ
                1
              
              ⁢
              
                
                  W
                  H
                
                ⁡
                
                  (
                  
                    
                      z
                      k
                    
                    -
                    
                      b
                      z
                      k
                    
                  
                  )
                
              
            
            +
            
              
                μ
                3
              
              ⁢
              
                
                  S
                  H
                
                ⁡
                
                  (
                  
                    
                      v
                      k
                    
                    -
                    
                      b
                      v
                      k
                    
                  
                  )
                
              
            
          
          ]
        
      
    
    ,
    
      

    
    ⁢
    
      
        z
        
          k
          +
          1
        
      
      =
      
        
          soft
          ⁡
          
            (
            
              
                
                  Wx
                  
                    k
                    +
                    1
                  
                
                +
                
                  b
                  z
                  k
                
              
              ,
              
                1
                
                  μ
                  1
                
              
            
            )
          
        
        ⁢
        
          
        
        ⁢
        where
      
    
  




  
    
      soft
      ⁡
      
        (
        
          x
          ,
          T
        
        )
      
    
    =
    
      {
      
        
          
            
              
                
                  
                    x
                    +
                    T
                  
                
                
                  
                    
                      
                        if
                        ⁢
                        
                          
                        
                        ⁢
                        x
                      
                      ≤
                      
                        -
                        T
                      
                    
                    ,
                  
                
              
              
                
                  0
                
                
                  
                    
                      
                        if
                        ⁢
                        
                          
                        
                        ⁢
                        
                          
                          x
                          
                        
                      
                      ≤
                      T
                    
                    ,
                  
                
              
              
                
                  
                    x
                    -
                    T
                  
                
                
                  
                    
                      
                        if
                        ⁢
                        
                          
                        
                        ⁢
                        x
                      
                      ≥
                      T
                    
                    ,
                  
                
              
            
            ⁢
            
              

            
            ⁢
            and
            ⁢
            
              

            
            ⁢
            
              v
              
                k
                +
                1
              
            
          
          =
          
            
              
                (
                
                  
                    
                      F
                      H
                    
                    ⁢
                    F
                  
                  +
                  
                    
                      μ
                      3
                    
                    ⁢
                    I
                  
                
                )
              
              
                -
                1
              
            
            ⁡
            
              [
              
                
                  
                    F
                    H
                  
                  ⁢
                  y
                
                +
                
                  
                    μ
                    3
                  
                  ⁡
                  
                    (
                    
                      
                        Sx
                        
                          k
                          +
                          1
                        
                      
                      +
                      
                        b
                        v
                        k
                      
                    
                    )
                  
                
              
              ]
            
          
        
        ,
      
    
  



where k is an iteration counter, μ1 and μ3 are parameters of an augmented Lagrangian function





  
    
      L
      ⁡
      
        (
        
          x
          ,
          z
          ,
          v
          ,
          
            b
            z
          
          ,
          
            b
            v
          
        
        )
      
    
    =
    
      
        
          1
          2
        
        ⁢
        
          
            
            
              Fv
              -
              y
            
            
          
          2
          2
        
      
      +
      
        λ
        ⁢
        
          
            
            z
            
          
          1
        
      
      +
      
        
          
            μ
            1
          
          2
        
        ⁢
        
          
            
            
              Wx
              -
              z
            
            
          
          2
          2
        
      
      +
      
        
          
            μ
            3
          
          2
        
        ⁢
        
          
            
            
              Sx
              -
              v
            
            
          
          2
          2
        
      
      +
      
        
          μ
          1
        
        ⁢
        
          〈
          
            
              b
              z
            
            ,
            
              Wx
              -
              z
              +
              y
            
          
          〉
        
      
      +
      
        
          μ
          3
        
        ⁢
        
          〈
          
            
              b
              v
            
            ,
            
              Sx
              -
              v
            
          
          〉
        
      
    
  
  ,




and bz and bv are dual variables of the augmented Lagrangian.

According to a further aspect of the invention, vk+1 can be updated as




  
    v
    
      k
      +
      1
    
  
  =
  
    
      
        (
        
          
            Sx
            
              k
              +
              1
            
          
          +
          
            b
            v
            k
          
        
        )
      
      +
      
        
          τ
          
            τ
            +
            1
          
        
        ⁢
        
          
            F
            H
          
          ⁡
          
            (
            
              y
              -
              
                F
                ⁡
                
                  (
                  
                    
                      Sx
                      
                        k
                        +
                        1
                      
                    
                    +
                    
                      b
                      v
                      k
                    
                  
                  )
                
              
            
            )
          
        
        ⁢
        
          
        
        ⁢
        where
        ⁢
        
          
        
        ⁢
        τ
      
    
    =
    
      1
      /
      
        
          μ
          3
        
        .
      
    
  




According to a further aspect of the invention, λ≦∥WAHy∥∞.
According to a further aspect of the invention, μ1=μ3<1.
According to a further aspect of the invention, the method includes updating the dual variables as bzk+1=bzk+(Wxk+1−zk+1) and bvk+1=bvk+(Sxk+1−vk+1).
According to a further aspect of the invention, xk, zk, and vk, and dual variables bzk and bvk are initialized to zero.
According to a further aspect of the invention, xk, zk, and vk are updated until a relative difference between a current iteration estimate and a previous iteration estimate fall below a predefined threshold.
According to another aspect of the invention, there is provide a method for reconstructing parallel magnetic resonance images (MRI), including providing a set of acquired k-space MR image data y, and finding a target MR image x that optimizes



  
    
      
        min
        x
      
      ⁢
      
        
          
          z
          
        
        1
      
    
    +
    
      
        S
        ɛ
      
      ⁡
      
        (
        u
        )
      
    
  




  
    
      
        s
        .
        t
        .
        
          
        
        ⁢
        z
      
      =
      Wx
    
    ,
    
      u
      =
      
        Fv
        -
        y
      
    
    ,
    
      v
      =
      Sx
    
    ,
  



where v=Sx and z=Wx where S is a diagonal matrix containing sensitivity maps of coil elements in an MR receiver array, F is an FFT matrix where FFH=I and H denotes a Hermitian adjoint matrix, W is a redundant Haar wavelet in matrix satisfying WTW=I, where I is an identity matrix, λ≧0 is a regularization parameter,





  
    
      S
      ɛ
    
    ⁡
    
      (
      u
      )
    
  
  =
  
    {
    
      
        
          
            0
            ,
          
        
        
          
            
              
                
                  
                  u
                  
                
                2
              
              ≤
              ɛ
            
            ,
          
        
      
      
        
          ∞
        
        
          
            
              
                
                  
                  u
                  
                
                2
              
              >
              ɛ
            
            ,
          
        
      
    
  




and ε represents an allowed discrepancy between the target image x and the observed k-space data y, by updating




  
    
      
        x
        
          k
          +
          1
        
      
      =
      
        
          
            (
            
              
                
                  μ
                  1
                
                ⁢
                I
              
              +
              
                
                  μ
                  3
                
                ⁢
                
                  S
                  H
                
                ⁢
                S
              
            
            )
          
          
            -
            1
          
        
        ⁡
        
          [
          
            
              
                μ
                1
              
              ⁢
              
                
                  W
                  H
                
                ⁡
                
                  (
                  
                    
                      z
                      k
                    
                    -
                    
                      b
                      z
                      k
                    
                  
                  )
                
              
            
            +
            
              
                μ
                3
              
              ⁢
              
                
                  S
                  H
                
                ⁡
                
                  (
                  
                    
                      v
                      k
                    
                    -
                    
                      b
                      v
                      k
                    
                  
                  )
                
              
            
          
          ]
        
      
    
    ,
    
      

    
    ⁢
    
      
        z
        
          k
          +
          1
        
      
      =
      
        
          soft
          ⁡
          
            (
            
              
                
                  Wx
                  
                    k
                    +
                    1
                  
                
                +
                
                  b
                  z
                  k
                
              
              ,
              
                1
                
                  μ
                  1
                
              
            
            )
          
        
        ⁢
        
          
        
        ⁢
        where
      
    
  




  
    
      soft
      ⁡
      
        (
        
          x
          ,
          T
        
        )
      
    
    =
    
      {
      
        
          
            
              
                
                  
                    x
                    +
                    T
                  
                
                
                  
                    
                      
                        if
                        ⁢
                        
                          
                        
                        ⁢
                        x
                      
                      ≤
                      
                        -
                        T
                      
                    
                    ,
                  
                
              
              
                
                  0
                
                
                  
                    
                      
                        if
                        ⁢
                        
                          
                        
                        ⁢
                        
                          
                          x
                          
                        
                      
                      ≤
                      T
                    
                    ,
                  
                
              
              
                
                  
                    x
                    -
                    T
                  
                
                
                  
                    
                      
                        if
                        ⁢
                        
                          
                        
                        ⁢
                        x
                      
                      ≥
                      T
                    
                    ,
                    ,
                  
                
              
            
            ⁢
            
              

            
            ⁢
            
              v
              
                k
                +
                1
              
            
          
          =
          
            
              
                (
                
                  
                    
                      μ
                      2
                    
                    ⁢
                    
                      F
                      H
                    
                    ⁢
                    F
                  
                  +
                  
                    
                      μ
                      3
                    
                    ⁢
                    I
                  
                
                )
              
              
                -
                1
              
            
            ⁡
            
              [
              
                
                  
                    μ
                    2
                  
                  ⁡
                  
                    (
                    
                      
                        F
                        H
                      
                      ⁡
                      
                        (
                        
                          y
                          +
                          
                            u
                            k
                          
                          +
                          
                            b
                            u
                            k
                          
                        
                        )
                      
                    
                    )
                  
                
                +
                
                  
                    μ
                    3
                  
                  ⁡
                  
                    (
                    
                      
                        Sx
                        
                          k
                          +
                          1
                        
                      
                      +
                      
                        b
                        v
                        k
                      
                    
                    )
                  
                
              
              ]
            
          
        
        ,
        
          

        
        ⁢
        
          
            and
            ⁢
            
              

            
            ⁢
            
              u
              
                k
                +
                1
              
            
          
          =
          
            
              
                shrink
                ⁡
                
                  (
                  
                    
                      
                        Fv
                        
                          k
                          +
                          1
                        
                      
                      -
                      y
                      -
                      
                        b
                        u
                        k
                      
                    
                    ,
                    ɛ
                  
                  )
                
              
              ⁢
              
                
              
              ⁢
              where
              ⁢
              
                

              
              ⁢
              
                shrink
                ⁡
                
                  (
                  
                    x
                    ,
                    T
                  
                  )
                
              
            
            =
            
              {
              
                
                  
                    0
                  
                  
                    
                      
                        
                          if
                          ⁢
                          
                            
                          
                          ⁢
                          
                            
                            x
                            
                          
                        
                        ≤
                        T
                      
                      ,
                    
                  
                
                
                  
                    x
                  
                  
                    
                      
                        
                          if
                          ⁢
                          
                            
                          
                          ⁢
                          
                            
                            x
                            
                          
                        
                        >
                        T
                      
                      ,
                      ,
                    
                  
                
              
            
          
        
      
    
  



where k is an iteration counter, μ1, μ2 and μ3 are parameters of an augmented Lagrangian function





  
    
      L
      ⁡
      
        (
        
          x
          ,
          z
          ,
          u
          ,
          v
          ,
          
            b
            z
          
          ,
          
            b
            u
          
          ,
          
            b
            v
          
        
        )
      
    
    =
    
      
        
          
          z
          
        
        1
      
      +
      
        
          S
          ɛ
        
        ⁡
        
          (
          u
          )
        
      
      +
      
        
          
            μ
            1
          
          2
        
        ⁢
        
          
            
            
              Wx
              -
              z
            
            
          
          2
          2
        
      
      +
      
        
          
            μ
            2
          
          2
        
        ⁢
        
          
            
            
              Fv
              -
              y
              -
              u
            
            
          
          2
          2
        
      
      +
      
        
          
            μ
            3
          
          2
        
        ⁢
        
          
            
            
              Sx
              -
              v
            
            
          
          2
          2
        
      
      +
      
        
          μ
          1
        
        ⁢
        
          〈
          
            
              b
              z
            
            ,
            
              Wx
              -
              z
            
          
          〉
        
      
      +
      
        
          μ
          2
        
        ⁢
        
          〈
          
            
              b
              u
            
            ,
            
              u
              -
              Fv
              +
              y
            
          
          〉
        
      
      +
      
        
          μ
          3
        
        ⁢
        
          〈
          
            
              b
              v
            
            ,
            
              Sx
              -
              v
            
          
          〉
        
      
    
  
  ,




and bz, bu and bv are dual variables of the augmented Lagrangian.

According to a further aspect of the invention, the method includes updating the dual variables as bzk+1=bzk+(Wxk+1−zk+1), buk+1=buk+(uk+1−Fvk+1+y), and bvk+1=bvk+(Sxk+1−vk+1).
According to a further aspect of the invention, ε≦∥y∥2.
According to a further aspect of the invention, μ1, μ2, and μ3 are set as μ1=μ3=0.1ρ and μ2=ρ where




  ρ
  =
  
    
      1
      
        0.01
        ⁢
        
          
            
            
              
                WA
                H
              
              ⁢
              y
            
            
          
          ∞
        
      
    
    .
  




According to a further aspect of the invention, xk, zk, vk, and uk, and dual variables bzk, buk, and bvk are initialized to zero.
According to a further aspect of the invention, xk, zk, vk and uk are updated until a relative difference between a current iteration estimate and a previous iteration estimate fall below a predefined threshold.
According to another aspect of the invention, there is provided a non-transitory program storage device readable by a computer, tangibly embodying a program of instructions executed by the computer to perform the method steps for reconstructing parallel magnetic resonance images (MRI).



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a flowchart of an unconstrained ADMM algorithm according to an embodiment of the invention.
FIG. 2 is a flowchart of a constrained ADMM algorithm according to an embodiment of the invention.
FIGS. 3(a)-(b) illustrates values for λWAHy∥∞ and ∥AHy∥∞, according to an embodiment of the invention.
FIGS. 4(a)-(b) illustrates parallel MRI reconstruction by FISTA and ADMM on a scanned phantom, according to an embodiment of the invention.
FIGS. 5(a)-(b) illustrates parallel MRI reconstruction by FISTA and ADMM on an in-vivo brain image, according to an embodiment of the invention.
FIG. 6 is a block diagram of an exemplary computer system for implementing an ADMM algorithm for parallel MRI reconstruction, according to an embodiment of the invention.



DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS
Exemplary embodiments of the invention as described herein generally include systems and methods for alternating direction of multipliers (ADMM) for parallel MRI reconstruction. Accordingly, while the invention is susceptible to various modifications and alternative forms, specific embodiments thereof are shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that there is no intent to limit the invention to the particular forms disclosed, but on the contrary, the invention is to cover all modifications, equivalents, and alternatives falling within the spirit and scope of the invention.
As used herein, the term “image” refers to multi-dimensional data composed of discrete image elements (e.g., pixels for 2-dimensional images and voxels for 3-dimensional images). The image may be, for example, a medical image of a subject collected by computer tomography, magnetic resonance imaging, ultrasound, or any other medical imaging system known to one of skill in the art. The image may also be provided from non-medical contexts, such as, for example, remote sensing systems, electron microscopy, etc. Although an image can be thought of as a function from R3 to R or R7, the methods of the inventions are not limited to such images, and can be applied to images of any dimension, e.g., a 2-dimensional picture or a 3-dimensional volume. For a 2- or 3-dimensional image, the domain of the image is typically a 2- or 3-dimensional rectangular array, wherein each pixel or voxel can be addressed with reference to a set of 2 or 3 mutually orthogonal axes. The terms “digital” and “digitized” as used herein will refer to images or volumes, as appropriate, in a digital or digitized format acquired via a digital acquisition system or via conversion from an analog image.
An alternating direction of multipliers method (ADMM) has been proposed for solving both the unconstrained and constrained optimizations. According to embodiments of the invention, when applying ADMM to solve EQS. (6) and (7), auxiliary variables are introduced to split both the data fidelity term 1⁄2∥Ax−y∥22 and the regularization term λ∥Wx∥1. Embodiments of the invention can update all variables, both primal and dual, in closed form, and use redundant Haar wavelets to save a set of variables.
Embodiments of the invention can solve EQ. (6) by introducing a splitting variable

v=Sx, 

for the data fidelity term, and

z=Wx 

for the l1 regularization term.

FIG. 1 is a flowchart of an unconstrained ADMM algorithm according to an embodiment of the invention. Referring now to the figure, given a set of acquired k-space MR image data y at step 11, according to an embodiment of the invention, EQ. (6) can be written as




  
    
      
        
          
            
              min
              x
            
            ⁢
            
              
                1
                2
              
              ⁢
              
                
                  
                  
                    Fv
                    -
                    y
                  
                  
                
                2
                2
              
            
          
          +
          
            λ
            ⁢
            
              
                
                z
                
              
              1
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              s
              .
              t
              .
              
                
              
              ⁢
              z
            
            =
            Wx
          
          ,
          
            v
            =
            
              Sx
              .
            
          
        
      
    
    
      
        (
        8
        )
      
    
  




According to an embodiment of the invention, the augmented Lagrangian of EQ. (8) can be written as





  
    
      
        
          L
          ⁡
          
            (
            
              x
              ,
              z
              ,
              v
              ,
              
                b
                z
              
              ,
              
                b
                v
              
            
            )
          
        
        =
        
          
            
              1
              2
            
            ⁢
            
              
                
                
                  Fv
                  -
                  y
                
                
              
              2
              2
            
          
          +
          
            λ
            ⁢
            
              
                
                z
                
              
              1
            
          
          +
          
            
              
                μ
                1
              
              2
            
            ⁢
            
              
                
                
                  Wx
                  -
                  z
                
                
              
              2
              2
            
          
          +
          
            
              
                μ
                3
              
              2
            
            ⁢
            
              
                
                
                  Sx
                  -
                  v
                
                
              
              2
              2
            
          
          +
          
            
              μ
              1
            
            ⁢
            
              〈
              
                
                  b
                  z
                
                ,
                
                  Wx
                  -
                  z
                  +
                  y
                
              
              〉
            
          
          +
          
            
              μ
              3
            
            ⁢
            
              〈
              
                
                  b
                  v
                
                ,
                
                  Sx
                  -
                  v
                
              
              〉
            
          
        
      
    
    
      
        (
        9
        )
      
    
  




where x, z, v are primal variables, and bz, bv are dual variables.

A conventional augmented Lagrangian (AL) updates the primal variables by solving




  
    
      
        
          (
          
            
              x
              
                k
                +
                1
              
            
            ,
            
              z
              
                k
                +
                1
              
            
            ,
            
              v
              
                k
                +
                1
              
            
          
          )
        
        =
        
          
            
              arg
              ⁢
              
                
              
              ⁢
              min
            
            
              x
              ,
              z
              ,
              v
            
          
          ⁢
          
            
          
          ⁢
          
            L
            ⁡
            
              (
              
                x
                ,
                z
                ,
                v
                ,
                
                  b
                  z
                  k
                
                ,
                
                  b
                  v
                  k
                
              
              )
            
          
        
      
    
    
      
        (
        10
        )
      
    
  




A conjugate gradient method may be used to solve EQ. (10), however, this can be computationally expensive.

In an ADMM according to an embodiment of the invention, a given primal variable may be updated by fixing other variables as follows:




  
    
      
        
          x
          
            k
            +
            1
          
        
        =
        
          
            
              arg
              ⁢
              
                
              
              ⁢
              min
            
            x
          
          ⁢
          
            
          
          ⁢
          
            L
            ⁡
            
              (
              
                x
                ,
                
                  z
                  k
                
                ,
                
                  v
                  k
                
                ,
                
                  b
                  z
                  k
                
                ,
                
                  b
                  v
                  k
                
              
              )
            
          
        
      
    
    
      
        (
        11
        )
      
    
  
  
    
      
        
          z
          
            k
            +
            1
          
        
        =
        
          
            
              arg
              ⁢
              
                
              
              ⁢
              min
            
            x
          
          ⁢
          
            
          
          ⁢
          
            L
            ⁡
            
              (
              
                
                  x
                  
                    k
                    +
                    1
                  
                
                ,
                z
                ,
                
                  v
                  k
                
                ,
                
                  b
                  z
                  k
                
                ,
                
                  b
                  v
                  k
                
              
              )
            
          
        
      
    
    
      
        (
        12
        )
      
    
  
  
    
      
        
          v
          
            k
            +
            1
          
        
        =
        
          
            
              arg
              ⁢
              
                
              
              ⁢
              min
            
            x
          
          ⁢
          
            
          
          ⁢
          
            L
            ⁡
            
              (
              
                
                  x
                  
                    k
                    +
                    1
                  
                
                ,
                
                  z
                  
                    k
                    +
                    1
                  
                
                ,
                v
                ,
                
                  b
                  z
                  k
                
                ,
                
                  b
                  v
                  k
                
              
              )
            
          
        
      
    
    
      
        (
        13
        )
      
    
  




Due to the introduction of the splitting variables z and v, all of the primal variables can be updated in closed form as, with reference to the steps of FIG. 1:





  
    
      
        
          
            x
            
              k
              +
              1
            
          
          =
          
            
              
                (
                
                  
                    
                      μ
                      1
                    
                    ⁢
                    I
                  
                  +
                  
                    
                      μ
                      3
                    
                    ⁢
                    
                      S
                      H
                    
                    ⁢
                    S
                  
                
                )
              
              
                -
                1
              
            
            ⁡
            
              [
              
                
                  
                    μ
                    1
                  
                  ⁢
                  
                    
                      W
                      H
                    
                    ⁡
                    
                      (
                      
                        
                          z
                          k
                        
                        -
                        
                          b
                          z
                          k
                        
                      
                      )
                    
                  
                
                +
                
                  
                    μ
                    3
                  
                  ⁢
                  
                    
                      S
                      H
                    
                    ⁡
                    
                      (
                      
                        
                          v
                          k
                        
                        -
                        
                          b
                          v
                          k
                        
                      
                      )
                    
                  
                
              
              ]
            
          
        
        ,
      
    
    
      
        
          (
          
            step
            ⁢
            
              
            
            ⁢
            13
          
          )
        
        ⁢
        
          (
          14
          )
        
      
    
  
  
    
      
        
          
        
        ⁢
        
          
            
              z
              
                k
                +
                1
              
            
            =
            
              soft
              (
              
                
                  
                    
                      W
                      ⁢
                      x
                    
                    
                      k
                      +
                      1
                    
                  
                  +
                  
                    b
                    z
                    k
                  
                
                ,
                
                  1
                  
                    μ
                    1
                  
                
              
              )
            
          
          ,
        
      
    
    
      
        
          (
          
            step
            ⁢
            
              
            
            ⁢
            14
          
          )
        
        ⁢
        
          (
          15
          )
        
      
    
  
  
    
      
        
          
        
        ⁢
        
          
            
              v
              
                k
                +
                1
              
            
            =
            
              
                
                  (
                  
                    
                      
                        F
                        H
                      
                      ⁢
                      F
                    
                    +
                    
                      
                        μ
                        3
                      
                      ⁢
                      I
                    
                  
                  )
                
                
                  -
                  1
                
              
              ⁡
              
                [
                
                  
                    
                      F
                      H
                    
                    ⁢
                    y
                  
                  +
                  
                    
                      μ
                      3
                    
                    ⁡
                    
                      (
                      
                        
                          Sx
                          
                            k
                            +
                            1
                          
                        
                        +
                        
                          b
                          v
                          k
                        
                      
                      )
                    
                  
                
                ]
              
            
          
          ,
        
      
    
    
      
        
          (
          
            step
            ⁢
            
              
            
            ⁢
            15
          
          )
        
        ⁢
        
          (
          16
          )
        
      
    
  
  
    
      
        
          
        
        ⁢
        
          
            where
            ⁢
            
              
            
            ⁢
            
              soft
              ⁡
              
                (
                
                  x
                  ,
                  T
                
                )
              
            
          
          =
          
            {
            
              
                
                  
                    
                      x
                      +
                      T
                    
                  
                  
                    
                      
                        
                          if
                          ⁢
                          
                            
                          
                          ⁢
                          x
                        
                        ≤
                        
                          -
                          T
                        
                      
                      ,
                    
                  
                
                
                  
                    0
                  
                  
                    
                      
                        
                          if
                          ⁢
                          
                            
                          
                          ⁢
                          
                            
                            x
                            
                          
                        
                        ≤
                        T
                      
                      ,
                    
                  
                
                
                  
                    
                      x
                      -
                      T
                    
                  
                  
                    
                      
                        
                          if
                          ⁢
                          
                            
                          
                          ⁢
                          x
                        
                        ≥
                        T
                      
                      ,
                    
                  
                
              
              ⁢
              
                

              
              ⁢
              
                
              
              ⁢
              is
              ⁢
              
                
              
              ⁢
              the
              ⁢
              
                
              
              ⁢
              soft
              ⁢
              
                
              
              ⁢
              shrinkage
              ⁢
              
                
              
              ⁢
              
                operator
                .
              
            
          
        
      
    
    
      
        
      
    
  




Since S is a diagonal matrix, (μ1I+μ3SHS)−1 can be computed in linear time. In addition, if the coil sensitivity maps are normalized so that SHS=I, this computation can be further simplified.
By using




  
    
      
        (
        
          I
          +
          
            τ
            ⁢
            
              
            
            ⁢
            
              F
              H
            
            ⁢
            F
          
        
        )
      
      
        -
        1
      
    
    =
    
      I
      -
      
        τ
        ⁢
        
          
            
              F
              H
            
            ⁢
            F
          
          
            τ
            +
            1
          
        
      
    
  
  ,




embodiments of the invention can rewrite vk+1 as





  
    
      
        
          
            v
            
              k
              +
              1
            
          
          =
          
            
              (
              
                
                  Sx
                  
                    k
                    +
                    1
                  
                
                +
                
                  b
                  v
                  k
                
              
              )
            
            +
            
              
                τ
                
                  τ
                  +
                  1
                
              
              ⁢
              
                
                  F
                  H
                
                ⁡
                
                  (
                  
                    y
                    -
                    
                      F
                      ⁡
                      
                        (
                        
                          
                            Sx
                            
                              k
                              +
                              1
                            
                          
                          +
                          
                            b
                            v
                            k
                          
                        
                        )
                      
                    
                  
                  )
                
              
            
          
        
        ,
      
    
    
      
        (
        17
        )
      
    
  
  
    
      
        
          where
          ⁢
          
            
          
          ⁢
          τ
        
        =
        
          1
          /
          
            
              μ
              3
            
            .
          
        
      
    
    
      
        
      
    
  




Referring again to FIG. 1, according to an embodiment of the invention, the dual variables can be updated by dual ascent as follows, with reference to the steps of FIG. 1:

bzk+1=bzk+(Wxk+1−zk+1),  (step 16)(18)

bvk+1=bvk+(Sxk+1−vk+1),  (step 17)(19)

Steps 13 to 17 will be repeated from step 18 until convergence.

According to an embodiment of the invention, each iteration costs: (1) one operation of S and operation of SH, whose cost is linear in n, the image size and c, the number of coils; (2) c operations of Fμ and FuH, and these two operations can be computed in n log(n) time, where n is the image size; and (3) one operation of W and one operation of WH, whose computational cost is linear in n, the image size. Therefore, according to an embodiment of the invention, the per iteration cost is cn log(n).
According to an embodiment of the invention, to solve EQ. (7), let




  
    
      
        
          
            S
            ɛ
          
          ⁡
          
            (
            u
            )
          
        
        =
        
          {
          
            
              
                
                  0
                  ,
                
              
              
                
                  
                    
                      
                        
                        u
                        
                      
                      2
                    
                    ≤
                    ɛ
                  
                  ,
                
              
            
            
              
                ∞
              
              
                
                  
                    
                      
                        
                        u
                        
                      
                      2
                    
                    >
                    ɛ
                  
                  ,
                
              
            
          
        
      
    
    
      
        (
        20
        )
      
    
  




and introduce the splitting variables

u=Fv−y, 

v=Sx, 

z=Wx. 

FIG. 2 is a flowchart of a constrained ADMM algorithm according to an embodiment of the invention. Referring now to the figure, given a set of acquired k-space MR image data y at step 21, EQ. (7) can be written according to an embodiment of the invention as




  
    
      
        
          
            
              min
              x
            
            ⁢
            
              
                
                z
                
              
              1
            
          
          +
          
            
              S
              ɛ
            
            ⁡
            
              (
              u
              )
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              s
              .
              t
              .
              
                
              
              ⁢
              z
            
            =
            Wx
          
          ,
          
            u
            =
            
              Fv
              -
              y
            
          
          ,
          
            v
            =
            
              Sx
              .
            
          
        
      
    
    
      
        (
        21
        )
      
    
  




According to an embodiment of the invention, the augmented Lagrangian of EQ. (15) can be written as





  
    
      
        
          L
          ⁡
          
            (
            
              x
              ,
              z
              ,
              u
              ,
              v
              ,
              
                b
                z
              
              ,
              
                b
                u
              
              ,
              
                b
                v
              
            
            )
          
        
        =
        
          
            
              
              z
              
            
            1
          
          +
          
            
              S
              ɛ
            
            ⁡
            
              (
              u
              )
            
          
          +
          
            
              
                μ
                1
              
              2
            
            ⁢
            
              
                
                
                  Wx
                  -
                  z
                
                
              
              2
              2
            
          
          +
          
            
              
                μ
                2
              
              2
            
            ⁢
            
              
                
                
                  Fv
                  -
                  y
                  -
                  u
                
                
              
              2
              2
            
          
          +
          
            
              
                μ
                3
              
              2
            
            ⁢
            
              
                
                
                  Sx
                  -
                  v
                
                
              
              2
              2
            
          
          +
          
            
              μ
              1
            
            ⁢
            
              〈
              
                
                  b
                  z
                
                ,
                
                  Wx
                  -
                  z
                
              
              〉
            
          
          +
          
            
              μ
              2
            
            ⁢
            
              〈
              
                
                  b
                  u
                
                ,
                
                  u
                  -
                  Fv
                  +
                  y
                
              
              〉
            
          
          +
          
            
              μ
              3
            
            ⁢
            
              
                〈
                
                  
                    b
                    v
                  
                  ,
                  
                    Sx
                    -
                    v
                  
                
                〉
              
              .
            
          
        
      
    
    
      
        (
        22
        )
      
    
  




Embodiments can update the primal variables as follows, with reference to the steps of FIG. 2:




  
    
      
        
          
            x
            
              k
              +
              1
            
          
          =
          
            
              
                (
                
                  
                    
                      μ
                      1
                    
                    ⁢
                    I
                  
                  +
                  
                    
                      μ
                      3
                    
                    ⁢
                    
                      S
                      H
                    
                    ⁢
                    S
                  
                
                )
              
              
                -
                1
              
            
            ⁡
            
              [
              
                
                  
                    μ
                    1
                  
                  ⁢
                  
                    
                      W
                      H
                    
                    ⁡
                    
                      (
                      
                        
                          z
                          k
                        
                        -
                        
                          b
                          z
                          k
                        
                      
                      )
                    
                  
                
                +
                
                  
                    μ
                    3
                  
                  ⁢
                  
                    
                      S
                      H
                    
                    ⁡
                    
                      (
                      
                        
                          v
                          k
                        
                        -
                        
                          b
                          v
                          k
                        
                      
                      )
                    
                  
                
              
              ]
            
          
        
        ,
      
    
    
      
        
          (
          
            step
            ⁢
            
              
            
            ⁢
            22
          
          )
        
        ⁢
        
          (
          23
          )
        
      
    
  
  
    
      
        
          
        
        ⁢
        
          
            
              z
              
                k
                +
                1
              
            
            =
            
              soft
              (
              
                
                  
                    
                      W
                      ⁢
                      x
                    
                    
                      k
                      +
                      1
                    
                  
                  +
                  
                    b
                    z
                    k
                  
                
                ,
                
                  1
                  
                    μ
                    1
                  
                
              
              )
            
          
          ,
        
      
    
    
      
        
          (
          
            step
            ⁢
            
              
            
            ⁢
            23
          
          )
        
        ⁢
        
          (
          24
          )
        
      
    
  
  
    
      
        
          v
          
            k
            +
            1
          
        
        =
        
          
            
              (
              
                
                  
                    μ
                    2
                  
                  ⁢
                  
                    F
                    H
                  
                  ⁢
                  F
                
                +
                
                  
                    μ
                    3
                  
                  ⁢
                  I
                
              
              )
            
            
              -
              1
            
          
          ⁡
          
            [
            
              
                
                  μ
                  2
                
                ⁡
                
                  (
                  
                    
                      F
                      H
                    
                    ⁡
                    
                      (
                      
                        y
                        +
                        
                          u
                          k
                        
                        +
                        
                          b
                          u
                          k
                        
                      
                      )
                    
                  
                  )
                
              
              +
              
                
                  μ
                  3
                
                ⁡
                
                  (
                  
                    
                      Sx
                      
                        k
                        +
                        1
                      
                    
                    +
                    
                      b
                      v
                      k
                    
                  
                  )
                
              
            
            ]
          
        
      
    
    
      
        
          (
          
            step
            ⁢
            
              
            
            ⁢
            24
          
          )
        
        ⁢
        
          (
          25
          )
        
      
    
  
  
    
      
        
          
        
        ⁢
        
          
            u
            
              k
              +
              1
            
          
          =
          
            shrink
            (
            
              
                
                  
                    F
                    ⁢
                    v
                  
                  
                    k
                    +
                    1
                  
                
                -
                y
                -
                
                  b
                  u
                  k
                
              
              ,
              ɛ
            
            )
          
        
      
    
    
      
        
          (
          
            step
            ⁢
            
              
            
            ⁢
            25
          
          )
        
        ⁢
        
          (
          26
          )
        
      
    
  




and can update the dual variables as follows:

bzk+1=bzk+(Wxk+1−zk+1),  (step 26)(27)

buk+1=buk+(uk+1−Fvk+1+y),  (step 27)(28)

bvk+1=bvk+(Sxk+1−vk+1),  (step 28)(29)

As in an unconstrained embodiment, steps 22 to 28 can be repeated from step 29 until convergence.

In the above constrained and unconstrained formulations according to embodiments of the invention, both the primal and dual variables can be initialized to zero. Note that the FFT and redundant Haar matrices F and W are fixed, standard quantities. One exemplary, non-limiting convergence criteria for stopping the iterations is when the relative difference between current iteration estimate and the previous iteration estimate is below a certain threshold.
According to an embodiment of the invention, an analysis similar to that conducted for the solution of EQ. (6) yields a per iteration cost to also be cn log(n).
According to an embodiment of the invention, parameters can be set in a data-dependent manner.
Parameter λ:
In the unconstrained EQ. (6), embodiments of the invention can set λ as a ratio of λmax defined as:

λmax=∥WAHy∥∞.  (30)

Theorem 1:

For the unconstrained EQ. (6), if λ≧λmax defined in EQ. (30), then the solution of EQ. (6) is zero.
Proof:
According to an embodiment of the invention, the optimality condition of EQ. (6) is as follows: x* is an optimal solution of EQ. (6) if and only if

0εAHAx*−AHy+λWHSGN(Wx*)  (31)

where SGN( ) is the sign function.

If λ≧λmax, one has

WAHyελSGN(0).

Therefore,

AHyελWHSGN(0).

Thus, it follows from EQ. (31) that zero is a solution of EQ. (6). □

Theorem 1 provides a data dependent maximal value for λ, i.e., λ≦∥WAHy∥∞. This λmax is dependent on the k-space observations y, the coil sensitivity maps S, and the sampling patterns specified by F.
FIGS. 3(a)-(b) illustrates experimentally obtained values for ∥WAHy∥∞ and ∥AHy∥∞, according to an embodiment of the invention, and show that the following relationship usually holds:

∥WAHy∥∞<∥AHy∥∞  (32)

Strictly speaking, the above inequality does not hold mathematically, e.g., when y=0, the left hand side and the right hand side are equal. However, according to an embodiment of the invention, the empirical finding of EQ. (32) enables one to finely tune the parameter λ. When the entries are generated from a uniform distribution over [0,1], there is almost no change in ∥AHy∥∞, while ∥WAHy∥∞ can capture such as change in AHy.

Furthermore, if λ is set in the interval ∥AHy∥∞[0,1], as shown in FIG. 3(a), almost half of the interval is useless. Experimental results according to embodiments of the invention show that an optimal value for λ usually lies in the interval λmax[0.001, 0.02].
Parameter ε:
For the constrained optimization of EQ. (7), embodiments of the invention can define

εmax=∥y∥2.  (33)

Theorem 2:

When ε≧εmax, zero is a solution to EQ. (7).
Proof:
When ε≧εmax, zero is clearly a solution to EQ. (7). □
Parameters μ1, μ3 for Unconstrained ADMM Variable Split:
According to an embodiment of the invention, it follows from EQ. (9) that: (1) large values of μ1 and μ3 place too much emphasis on the equality constraints Wx=z and Sx=v, but not enough on the data fidelity term 1⁄2∥Fv−y∥22; and (2) small values of μ1 and μ3 primarily emphasize the data fidelity term 1⁄2∥Fv−y∥22 but insufficiently emphasize the equality constraints Wx=z and Sx=v. Theoretically, for any μ1, μ3>0, an unconstrained ADMM variable split according to an embodiment of the invention is guaranteed to converge, but its efficiency depends on the choice of μ1 and μ3.
In an unconstrained ADMM variable split according to an embodiment of the invention, μ1 and μ3 are set as μ1=μ3=0.1 based on the following considerations: (1) for 1⁄2∥Wx−z∥22 and 1⁄2∥Sx−v∥22, the maximal eigenvalues of the Hessian matrices are all identity matrices, thus embodiments may set μ1=μ3; and (2) 1⁄2∥Fv−y∥22, being the data fidelity term, needs to be given a high weight, which implies setting μ1 and μ3 to a value less than 1.
Parameters μ1, μ2, μ3 for the Constrained ADMM Variable Split:
According to an embodiment of the invention, it follows from EQ. (22) that: (1) large values of μ1, μ2, and μ3 de-emphasize the l1 penalty; and (2) small values of μ1, μ2, and μ3 do not handle well the equality constraints Wx=z, u=Fv−y, and Sx=v for at least the first few iterations. Theoretically, for any μ1, μ2, μ3>0, a constrained ADMM variable split according to an embodiment of the invention is guaranteed to converge, but its efficiency depends on the choice of μ1, μ2, and μ3.
According to an embodiment of the invention,




  
    ρ
    =
    
      1
      
        0.01
        ⁢
        
          λ
          max
        
      
    
  
  ,




where λmax is defined as in EQ. (30), i.e., λmax=∥WAHy∥∞. In a constrained ADMM variable split according to an embodiment of the invention, μ1, μ2, and μ3 are set as μ1=μ3=0.1ρ, μ2=ρ based on the following considerations: (1) for 1⁄2∥Wx−z∥22 and 1⁄2∥Sx−v∥22, the maximal eigenvalues of the Hessian matrices are all identity matrices, thus embodiments may set μ1=μ3; (2) 1⁄2∥Fv−y∥22, being the data fidelity term, needs to be given a high weight, which implies setting μ2=10μ1=10μ3; (3) Sε(u), being a set, is invariant to any parameter; and (4) to balance the term ∥z∥1 with the constraints, the related terms for z are





  
    
      
        
        z
        
      
      1
    
    +
    
      
        
          μ
          1
        
        2
      
      ⁢
      
        
          
          
            Wx
            -
            z
          
          
        
        2
        2
      
    
    +
    
      
        μ
        1
      
      ⁢
      
        〈
        
          
            b
            z
          
          ,
          
            Wx
            -
            z
          
        
        〉
      
    
  
  ,




and the soft shrinkage value is





  
    1
    
      μ
      1
    
  
  .




Experiments with an unconstrained optimization according to an embodiment of the invention indicate that





  
    1
    
      μ
      1
    
  
  =
  
    0.001
    ⁢
    
      λ
      max
    
  




can yield a good reconstructed image.

Experiments of a parallel MRI reconstruction according to an embodiment of the invention were conducted on two data sets, a scanned phantom and a set acquired from healthy volunteers on a 3.0T clinical MR scanner. Imaging parameters includes a field of view=300×300 mm2, matrix=256×256, 10 coil elements, and a flip angle=12°. FIGS. 4(a)-(b) shows reconstruction results for a FISTA algorithm (FIG. 4(a)) and an unconstrained ADMM variable split according to an embodiment of the invention (FIG. 4(b)) on the scanned phantom, and FIGS. 3(a)-(b) shows reconstruction results for a FISTA algorithm (FIG. 5(a)) and an unconstrained ADMM variable split according to an embodiment of the invention (FIG. 5(b)) on the an in-vivo brain image from a healthy volunteer.
It is to be understood that the present invention can be implemented in various forms of hardware, software, firmware, special purpose processes, or a combination thereof. In one embodiment, the present invention can be implemented in software as an application program tangible embodied on a computer readable program storage device. The application program can be uploaded to, and executed by, a machine comprising any suitable architecture.
FIG. 6 is a block diagram of an exemplary computer system for implementing an ADMM algorithm for parallel MRI reconstruction, according to an embodiment of the invention. Referring now to FIG. 6, a computer system 61 for implementing the present invention can comprise, inter alia, a central processing unit (CPU) 62, a memory 63 and an input/output (I/O) interface 64. The computer system 61 is generally coupled through the I/O interface 64 to a display 65 and various input devices 66 such as a mouse and a keyboard. The support circuits can include circuits such as cache, power supplies, clock circuits, and a communication bus. The memory 63 can include random access memory (RAM), read only memory (ROM), disk drive, tape drive, etc., or a combinations thereof. The present invention can be implemented as a routine 67 that is stored in memory 63 and executed by the CPU 62 to process the signal from the signal source 68. As such, the computer system 61 is a general purpose computer system that becomes a specific purpose computer system when executing the routine 67 of the present invention.
The computer system 61 also includes an operating system and micro instruction code. The various processes and functions described herein can either be part of the micro instruction code or part of the application program (or combination thereof) which is executed via the operating system. In addition, various other peripheral devices can be connected to the computer platform such as an additional data storage device and a printing device.
It is to be further understood that, because some of the constituent system components and method steps depicted in the accompanying figures can be implemented in software, the actual connections between the systems components (or the process steps) may differ depending upon the manner in which the present invention is programmed. Given the teachings of the present invention provided herein, one of ordinary skill in the related art will be able to contemplate these and similar implementations or configurations of the present invention.
While the present invention has been described in detail with reference to exemplary embodiments, those skilled in the art will appreciate that various modifications and substitutions can be made thereto without departing from the spirit and scope of the invention as set forth in the appended claims.

## Claims

1. A method for reconstructing parallel magnetic resonance images (MRI), comprising:
providing a set of acquired k-space MR image data y; and
finding a target MR image x that minimizes 1⁄2∥Fv−y∥22+λ∥z∥1 wherein v=Sx and z=Wx wherein S is a diagonal matrix containing sensitivity maps of coil elements in an MR receiver array, F is an FFT matrix wherein FFH=I and H denotes a Hermitian adjoint matrix, W is a redundant Haar wavelet matrix satisfying WTW=I, wherein I is an identity matrix, and λ≧0 is a regularization parameter, by updating




  
    
      
        x
        
          k
          +
          1
        
      
      =
      
        
          
            (
            
              
                
                  μ
                  1
                
                ⁢
                I
              
              +
              
                
                  μ
                  3
                
                ⁢
                
                  S
                  H
                
                ⁢
                S
              
            
            )
          
          
            -
            1
          
        
        ⁡
        
          [
          
            
              
                μ
                1
              
              ⁢
              
                
                  W
                  H
                
                ⁡
                
                  (
                  
                    
                      z
                      k
                    
                    -
                    
                      b
                      z
                      k
                    
                  
                  )
                
              
            
            +
            
              
                μ
                3
              
              ⁢
              
                
                  S
                  H
                
                ⁡
                
                  (
                  
                    
                      v
                      k
                    
                    -
                    
                      b
                      v
                      k
                    
                  
                  )
                
              
            
          
          ]
        
      
    
    ,
    
      

    
    ⁢
    
      
        z
        
          k
          +
          1
        
      
      =
      
        soft
        (
        
          
            
              
                W
                ⁢
                x
              
              
                k
                +
                1
              
            
            +
            
              b
              z
              k
            
          
          ,
          
            1
            
              μ
              1
            
          
        
        )
      
    
  




  
    
      wherein
      ⁢
      
        
      
      ⁢
      soft
      ⁢
      
        (
        
          x
          ,
          T
        
        )
      
    
    =
    
      {
      
        
          
            
              
                
                  
                    x
                    +
                    T
                  
                
                
                  
                    
                      
                        if
                        ⁢
                        
                          
                        
                        ⁢
                        x
                      
                      ≤
                      
                        -
                        T
                      
                    
                    ,
                  
                
              
              
                
                  0
                
                
                  
                    
                      
                        if
                        ⁢
                        
                          
                        
                        ⁢
                        
                          
                          x
                          
                        
                      
                      ≤
                      T
                    
                    ,
                  
                
              
              
                
                  
                    x
                    -
                    T
                  
                
                
                  
                    
                      
                        if
                        ⁢
                        
                          
                        
                        ⁢
                        x
                      
                      ≥
                      T
                    
                    ,
                  
                
              
            
            ⁢
            
              

            
            ⁢
            and
            ⁢
            
              

            
            ⁢
            
              v
              
                k
                +
                1
              
            
          
          =
          
            
              
                (
                
                  
                    
                      F
                      H
                    
                    ⁢
                    F
                  
                  +
                  
                    
                      μ
                      3
                    
                    ⁢
                    I
                  
                
                )
              
              
                -
                1
              
            
            ⁡
            
              [
              
                
                  
                    F
                    H
                  
                  ⁢
                  y
                
                +
                
                  
                    μ
                    3
                  
                  ⁡
                  
                    (
                    
                      
                        Sx
                        
                          k
                          +
                          1
                        
                      
                      +
                      
                        b
                        v
                        k
                      
                    
                    )
                  
                
              
              ]
            
          
        
        ,
      
    
  



wherein k is an iteration counter, μ1 and μ3 are parameters of an augmented Lagrangian function




  
    
      L
      ⁡
      
        (
        
          x
          ,
          z
          ,
          v
          ,
          
            b
            z
          
          ,
          
            b
            v
          
        
        )
      
    
    =
    
      
        
          1
          2
        
        ⁢
        
          
            
            
              Fv
              -
              y
            
            
          
          2
          2
        
      
      +
      
        λ
        ⁢
        
          
            
            z
            
          
          1
        
      
      +
      
        
          
            μ
            1
          
          2
        
        ⁢
        
          
            
            
              Wx
              -
              z
            
            
          
          2
          2
        
      
      +
      
        
          
            μ
            3
          
          2
        
        ⁢
        
          
            
            
              Sx
              -
              v
            
            
          
          2
          2
        
      
      +
      
        
          μ
          1
        
        ⁢
        
          〈
          
            
              b
              z
            
            ,
            
              Wx
              -
              z
              +
              y
            
          
          〉
        
      
      +
      
        
          μ
          3
        
        ⁢
        
          〈
          
            
              b
              v
            
            ,
            
              Sx
              -
              v
            
          
          〉
        
      
    
  
  ,




and bz and bv are dual variables of the augmented Lagrangian.

2. The method of claim 1, wherein vk+1 can be updated as



  
    
      v
      
        k
        +
        1
      
    
    =
    
      
        (
        
          
            Sx
            
              k
              +
              1
            
          
          +
          
            b
            v
            k
          
        
        )
      
      +
      
        
          τ
          
            τ
            +
            1
          
        
        ⁢
        
          
            F
            H
          
          ⁡
          
            (
            
              y
              -
              
                F
                ⁡
                
                  (
                  
                    
                      Sx
                      
                        k
                        +
                        1
                      
                    
                    +
                    
                      b
                      v
                      k
                    
                  
                  )
                
              
            
            )
          
        
        ⁢
        
          
        
        ⁢
        wherein
      
    
  




  
    τ
    =
    
      1
      /
      
        
          μ
          3
        
        .

3. The method of claim 1, wherein λ≦∥WAHy∥∞.

4. The method of claim 1, wherein μ1=μ3<1.

5. The method of claim 1, further comprising updating the dual variables as bzk+1=bzk+(Wxk+1−zk+1) and bvk+1=bvk+(Sxk+1−vk+1).

6. The method of claim 5, wherein xk, zk, and vk, and dual variables bzk and bvk are initialized to zero.

7. The method of claim 1, wherein xk, zk, and vk are updated until a relative difference between a current iteration estimate and a previous iteration estimate fall below a predefined threshold.

8. A method for reconstructing parallel magnetic resonance images (MRI), comprising:
providing a set of acquired k-space MR image data y; and
finding a target MR image x that optimizes




  
    
      
        min
        x
      
      ⁢
      
        
        
          z
          1
        
        
      
    
    +
    
      
        S
        ɛ
      
      ⁡
      
        (
        u
        )
      
    
  




  
    
      
        s
        .
        t
        .
        
          
        
        ⁢
        z
      
      =
      Wx
    
    ,
    
      u
      =
      
        Fv
        -
        y
      
    
    ,
    
      v
      =
      Sx
    
    ,
  



wherein v=Sx and z=Wx wherein S is a diagonal matrix containing sensitivity maps of coil elements in an MR receiver array, F is an FFT matrix wherein FFH=I and H denotes a Hermitian adjoint matrix, W is a redundant Haar wavelet matrix satisfying WTW=I, wherein I is an identity matrix, λ≧0 is a regularization parameter,




  
    
      S
      ɛ
    
    ⁡
    
      (
      u
      )
    
  
  =
  
    {
    
      
        
          
            0
            ,
          
        
        
          
            
              
                
                  
                  u
                  
                
                2
              
              ≤
              ɛ
            
            ,
          
        
      
      
        
          ∞
        
        
          
            
              
                
                  
                  u
                  
                
                2
              
              >
              ɛ
            
            ,
          
        
      
    
  




and ε represents an allowed discrepancy between the target image x and the observed k-space data y, by updating



  
    
      
        x
        
          k
          +
          1
        
      
      =
      
        
          
            (
            
              
                
                  μ
                  1
                
                ⁢
                I
              
              +
              
                
                  μ
                  3
                
                ⁢
                
                  S
                  H
                
                ⁢
                S
              
            
            )
          
          
            -
            1
          
        
        ⁡
        
          [
          
            
              
                μ
                1
              
              ⁢
              
                
                  W
                  H
                
                ⁡
                
                  (
                  
                    
                      z
                      k
                    
                    -
                    
                      b
                      z
                      k
                    
                  
                  )
                
              
            
            +
            
              
                μ
                3
              
              ⁢
              
                
                  S
                  H
                
                ⁡
                
                  (
                  
                    
                      v
                      k
                    
                    -
                    
                      b
                      v
                      k
                    
                  
                  )
                
              
            
          
          ]
        
      
    
    ,
    
      

    
    ⁢
    
      
        z
        
          k
          +
          1
        
      
      =
      
        
          soft
          ⁡
          
            (
            
              
                
                  Wx
                  
                    k
                    +
                    1
                  
                
                +
                
                  b
                  z
                  k
                
              
              ,
              
                1
                
                  μ
                  1
                
              
            
            )
          
        
        ⁢
        
          
        
        ⁢
        wherein
      
    
  




  
    
      soft
      ⁡
      
        (
        
          x
          ,
          T
        
        )
      
    
    =
    
      {
      
        
          
            
              
                
                  
                    x
                    +
                    T
                  
                
                
                  
                    
                      
                        if
                        ⁢
                        
                          
                        
                        ⁢
                        x
                      
                      ≤
                      
                        -
                        T
                      
                    
                    ,
                  
                
              
              
                
                  0
                
                
                  
                    
                      
                        if
                        ⁢
                        
                          
                        
                        ⁢
                        
                          
                          x
                          
                        
                      
                      ≤
                      T
                    
                    ,
                  
                
              
              
                
                  
                    x
                    -
                    T
                  
                
                
                  
                    
                      
                        if
                        ⁢
                        
                          
                        
                        ⁢
                        x
                      
                      ≥
                      T
                    
                    ,
                    ,
                  
                
              
            
            ⁢
            
              

            
            ⁢
            
              v
              
                k
                +
                1
              
            
          
          =
          
            
              
                (
                
                  
                    
                      μ
                      2
                    
                    ⁢
                    
                      F
                      H
                    
                    ⁢
                    F
                  
                  +
                  
                    
                      μ
                      3
                    
                    ⁢
                    I
                  
                
                )
              
              
                -
                1
              
            
            ⁡
            
              [
              
                
                  
                    μ
                    2
                  
                  ⁡
                  
                    (
                    
                      
                        F
                        H
                      
                      ⁡
                      
                        (
                        
                          y
                          +
                          
                            u
                            k
                          
                          +
                          
                            b
                            u
                            k
                          
                        
                        )
                      
                    
                    )
                  
                
                +
                
                  
                    μ
                    3
                  
                  ⁡
                  
                    (
                    
                      
                        Sx
                        
                          k
                          +
                          1
                        
                      
                      +
                      
                        b
                        v
                        k
                      
                    
                    )
                  
                
              
              ]
            
          
        
        ,
        
          

        
        ⁢
        
          
            and
            ⁢
            
              

            
            ⁢
            
              u
              
                k
                +
                1
              
            
          
          =
          
            
              
                shrink
                ⁡
                
                  (
                  
                    
                      
                        Fv
                        
                          k
                          +
                          1
                        
                      
                      -
                      y
                      -
                      
                        b
                        u
                        k
                      
                    
                    ,
                    ɛ
                  
                  )
                
              
              ⁢
              
                
              
              ⁢
              wherein
              ⁢
              
                

              
              ⁢
              
                shrink
                ⁡
                
                  (
                  
                    x
                    ,
                    T
                  
                  )
                
              
            
            =
            
              {
              
                
                  
                    0
                  
                  
                    
                      
                        
                          if
                          ⁢
                          
                            
                          
                          ⁢
                          
                            
                            x
                            
                          
                        
                        ≤
                        T
                      
                      ,
                    
                  
                
                
                  
                    x
                  
                  
                    
                      
                        if
                        ⁢
                        
                          
                        
                        ⁢
                        
                          
                          x
                          
                        
                        ⁢
                        T
                      
                      ,
                      ,
                    
                  
                
              
            
          
        
      
    
  


wherein k is an iteration counter, μ1, μ2 and μ3 are parameters of an augmented Lagrangian function





  
    
      L
      ⁡
      
        (
        
          x
          ,
          z
          ,
          u
          ,
          v
          ,
          
            b
            z
          
          ,
          
            b
            u
          
          ,
          
            b
            v
          
        
        )
      
    
    =
    
      
        
          
          z
          
        
        1
      
      +
      
        
          S
          ɛ
        
        ⁡
        
          (
          u
          )
        
      
      +
      
        
          
            μ
            1
          
          2
        
        ⁢
        
          
            
            
              Wx
              -
              z
            
            
          
          2
          2
        
      
      +
      
        
          
            μ
            2
          
          2
        
        ⁢
        
          
            
            
              Fv
              -
              y
              -
              u
            
            
          
          2
          2
        
      
      +
      
        
          
            μ
            3
          
          2
        
        ⁢
        
          
            
            
              Sx
              -
              v
            
            
          
          2
          2
        
      
      +
      
        
          μ
          1
        
        ⁢
        
          〈
          
            
              b
              z
            
            ,
            
              Wx
              -
              z
            
          
          〉
        
      
      +
      
        
          μ
          2
        
        ⁢
        
          〈
          
            
              b
              u
            
            ,
            
              u
              -
              Fv
              +
              y
            
          
          〉
        
      
      +
      
        
          μ
          3
        
        ⁢
        
          〈
          
            
              b
              v
            
            ,
            
              Sx
              -
              v
            
          
          〉
        
      
    
  
  ,




and bz, bu and bv are dual variables of the augmented Lagrangian.

9. The method of claim 8, further comprising updating the dual variables as


bzk+1=bzk+(Wxk+1−zk+1),



buk+1=buk+(uk+1−Fvk+1+y), and



bvk+1=bvk+(Sxk+1−vk+1).

10. The method of claim 8, wherein ε≦∥y∥2.

11. The method of claim 8, wherein μ1, μ2, and μ3 are set as μ1=μ3=0.1ρ and μ2=ρ wherein




  ρ
  =
  
    
      1
      
        0.01
        ⁢
        
          
            
            
              
                WA
                H
              
              ⁢
              y
            
            
          
          ∞
        
      
    
    .

12. The method of claim 9, wherein xk, zk, vk, and uk, and dual variables bzk, buk, and bvk are initialized to zero.

13. The method of claim 8, wherein xk, zk, vk and uk are updated until a relative difference between a current iteration estimate and a previous iteration estimate fall below a predefined threshold.

14. A non-transitory program storage device readable by a computer, tangibly embodying a program of instructions executed by the computer to perform the method steps for reconstructing parallel magnetic resonance images (MRI), the method comprising the steps of:
providing a set of acquired k-space MR image data y; and
finding a target MR image x that minimizes 1⁄2∥Fv−y∥22+λ∥z∥1 wherein v=Sx and z=Wx wherein S is a diagonal matrix containing sensitivity maps of coil elements in an MR receiver array, F is an FFT matrix wherein FFH=I and H denotes a Hermitian adjoint matrix, W is a redundant Haar wavelet matrix satisfying WTW=I, wherein I is an identity matrix, and λ≧0 is a regularization parameter, by updating




  
    
      
        x
        
          k
          +
          1
        
      
      =
      
        
          
            (
            
              
                
                  μ
                  1
                
                ⁢
                I
              
              +
              
                
                  μ
                  3
                
                ⁢
                
                  S
                  H
                
                ⁢
                S
              
            
            )
          
          
            -
            1
          
        
        ⁡
        
          [
          
            
              
                μ
                1
              
              ⁢
              
                
                  W
                  H
                
                ⁡
                
                  (
                  
                    
                      z
                      k
                    
                    -
                    
                      b
                      z
                      k
                    
                  
                  )
                
              
            
            +
            
              
                μ
                3
              
              ⁢
              
                
                  S
                  H
                
                ⁡
                
                  (
                  
                    
                      v
                      k
                    
                    -
                    
                      b
                      v
                      k
                    
                  
                  )
                
              
            
          
          ]
        
      
    
    ,
    
      

    
    ⁢
    
      
        z
        
          k
          +
          1
        
      
      =
      
        
          soft
          ⁡
          
            (
            
              
                
                  Wx
                  
                    k
                    +
                    1
                  
                
                +
                
                  b
                  z
                  k
                
              
              ,
              
                1
                
                  μ
                  1
                
              
            
            )
          
        
        ⁢
        
          
        
        ⁢
        wherein
      
    
  




  
    
      soft
      ⁡
      
        (
        
          x
          ,
          T
        
        )
      
    
    =
    
      {
      
        
          
            
              
                
                  
                    x
                    +
                    T
                  
                
                
                  
                    
                      
                        if
                        ⁢
                        
                          
                        
                        ⁢
                        x
                      
                      ≤
                      
                        -
                        T
                      
                    
                    ,
                  
                
              
              
                
                  0
                
                
                  
                    
                      
                        if
                        ⁢
                        
                          
                        
                        ⁢
                        
                          
                          x
                          
                        
                      
                      ≤
                      T
                    
                    ,
                  
                
              
              
                
                  
                    x
                    -
                    T
                  
                
                
                  
                    
                      
                        if
                        ⁢
                        
                          
                        
                        ⁢
                        x
                      
                      ≥
                      T
                    
                    ,
                  
                
              
            
            ⁢
            
              

            
            ⁢
            and
            ⁢
            
              

            
            ⁢
            
              v
              
                k
                +
                1
              
            
          
          =
          
            
              
                (
                
                  
                    
                      F
                      H
                    
                    ⁢
                    F
                  
                  +
                  
                    
                      μ
                      3
                    
                    ⁢
                    I
                  
                
                )
              
              
                -
                1
              
            
            ⁡
            
              [
              
                
                  
                    F
                    H
                  
                  ⁢
                  y
                
                +
                
                  
                    μ
                    3
                  
                  ⁡
                  
                    (
                    
                      
                        Sx
                        
                          k
                          +
                          1
                        
                      
                      +
                      
                        b
                        v
                        k
                      
                    
                    )
                  
                
              
              ]
            
          
        
        ,
      
    
  



wherein k is an iteration counter, μ1 and μ3 are parameters of an augmented Lagrangian function




  
    
      L
      ⁡
      
        (
        
          x
          ,
          z
          ,
          v
          ,
          
            b
            z
          
          ,
          
            b
            v
          
        
        )
      
    
    =
    
      
        
          1
          2
        
        ⁢
        
          
            
            
              Fv
              -
              y
            
            
          
          2
          2
        
      
      +
      
        λ
        ⁢
        
          
            
            z
            
          
          1
        
      
      +
      
        
          
            μ
            1
          
          2
        
        ⁢
        
          
            
            
              Wx
              -
              z
            
            
          
          2
          2
        
      
      +
      
        
          
            μ
            3
          
          2
        
        ⁢
        
          
            
            
              Sx
              -
              v
            
            
          
          2
          2
        
      
      +
      
        
          μ
          1
        
        ⁢
        
          〈
          
            
              b
              z
            
            ,
            
              Wx
              -
              z
              +
              y
            
          
          〉
        
      
      +
      
        
          μ
          3
        
        ⁢
        
          〈
          
            
              b
              v
            
            ,
            
              Sx
              -
              v
            
          
          〉
        
      
    
  
  ,




and bz and bv are dual variables of the augmented Lagrangian.

15. The computer readable program storage device of claim 14, wherein vk+1 can be updated as



  
    
      v
      
        k
        +
        1
      
    
    =
    
      
        (
        
          
            Sx
            
              k
              +
              1
            
          
          +
          
            b
            v
            k
          
        
        )
      
      +
      
        
          τ
          
            τ
            +
            1
          
        
        ⁢
        
          
            F
            H
          
          ⁡
          
            (
            
              y
              -
              
                F
                ⁡
                
                  (
                  
                    
                      Sx
                      
                        k
                        +
                        1
                      
                    
                    +
                    
                      b
                      v
                      k
                    
                  
                  )
                
              
            
            )
          
        
        ⁢
        
          
        
        ⁢
        wherein
      
    
  




  
    τ
    =
    
      1
      /
      
        
          μ
          3
        
        .

16. The computer readable program storage device of claim 14, wherein λ≦∥WAHy∥∞.

17. The computer readable program storage device of claim 14, wherein μ1=μ3<1.

18. The computer readable program storage device of claim 14, the method further comprising updating the dual variables as bzk+1=bzk+(Wxk+1−zk+1) and bvk+1=bvk+(Sxk+1−vk+1).

19. The computer readable program storage device of claim 18, wherein xk, zk, and vk, and dual variables bzk and bvk are initialized to zero.

20. The computer readable program storage device of claim 14, wherein xk, zk, and vk are updated until a relative difference between a current iteration estimate and a previous iteration estimate fall below a predefined threshold.

21. A non-transitory program storage device readable by a computer, tangibly embodying a program of instructions executed by the computer to perform the method steps for reconstructing parallel magnetic resonance images (MRI), the method comprising the steps of:
providing a set of acquired k-space MR image data y; and
finding a target MR image x that optimizes




  
    
      
        min
        x
      
      ⁢
      
        
          
          z
          
        
        1
      
    
    +
    
      
        S
        ɛ
      
      ⁡
      
        (
        u
        )
      
    
  




  
    
      
        s
        .
        t
        .
        
          
        
        ⁢
        z
      
      =
      Wx
    
    ,
    
      u
      =
      
        Fv
        -
        y
      
    
    ,
    
      v
      =
      
        Sx
        .
      
    
  



wherein v=Sx and z=Wx wherein S is a diagonal matrix containing sensitivity maps of coil elements in an MR receiver array, F is an FFT matrix wherein FFH=I and H denotes a Hermitian adjoint matrix, W is a redundant Haar wavelet matrix satisfying WTW=I, wherein I is an identity matrix, λ≧0 is a regularization parameter,




  
    
      S
      ɛ
    
    ⁡
    
      (
      u
      )
    
  
  =
  
    {
    
      
        
          
            0
            ,
          
        
        
          
            
              
                
                  
                  u
                  
                
                2
              
              ≤
              ɛ
            
            ,
          
        
      
      
        
          ∞
        
        
          
            
              
                
                  
                  u
                  
                
                2
              
              >
              ɛ
            
            ,
          
        
      
    
  




and ε represents an allowed discrepancy between the target image x and the observed k-space data y, by updating



  
    
      
    
    ⁢
    
      
        
          x
          
            k
            +
            1
          
        
        =
        
          
            
              (
              
                
                  
                    μ
                    1
                  
                  ⁢
                  I
                
                +
                
                  
                    μ
                    3
                  
                  ⁢
                  
                    S
                    H
                  
                  ⁢
                  S
                
              
              )
            
            
              -
              1
            
          
          ⁡
          
            [
            
              
                
                  μ
                  1
                
                ⁢
                
                  
                    W
                    H
                  
                  ⁡
                  
                    (
                    
                      
                        z
                        k
                      
                      -
                      
                        b
                        z
                        k
                      
                    
                    )
                  
                
              
              +
              
                
                  μ
                  3
                
                ⁢
                
                  
                    S
                    H
                  
                  ⁡
                  
                    (
                    
                      
                        v
                        k
                      
                      -
                      
                        b
                        v
                        k
                      
                    
                    )
                  
                
              
            
            ]
          
        
      
      ,
      
        

      
      ⁢
      
        
      
      ⁢
      
        
          z
          
            k
            +
            1
          
        
        =
        
          
            soft
            ⁡
            
              (
              
                
                  
                    Wx
                    
                      k
                      +
                      1
                    
                  
                  +
                  
                    b
                    z
                    k
                  
                
                ,
                
                  1
                  
                    μ
                    1
                  
                
              
              )
            
          
          ⁢
          
            
          
          ⁢
          wherein
        
      
    
  




  
    
      
    
    ⁢
    
      
        soft
        ⁡
        
          (
          
            x
            ,
            T
          
          )
        
      
      =
      
        {
        
          
            
              
                
                  
                    
                      x
                      +
                      T
                    
                  
                  
                    
                      
                        
                          if
                          ⁢
                          
                            
                          
                          ⁢
                          x
                        
                        ≤
                        
                          -
                          T
                        
                      
                      ,
                    
                  
                
                
                  
                    0
                  
                  
                    
                      
                        
                          if
                          ⁢
                          
                            
                          
                          ⁢
                          
                            
                            x
                            
                          
                        
                        ≤
                        T
                      
                      ,
                    
                  
                
                
                  
                    
                      x
                      -
                      T
                    
                  
                  
                    
                      
                        
                          if
                          ⁢
                          
                            
                          
                          ⁢
                          x
                        
                        ≥
                        T
                      
                      ,
                      ,
                    
                  
                
              
              ⁢
              
                

              
              ⁢
              
                v
                
                  k
                  +
                  1
                
              
            
            =
            
              
                
                  (
                  
                    
                      
                        μ
                        2
                      
                      ⁢
                      
                        F
                        H
                      
                      ⁢
                      F
                    
                    +
                    
                      
                        μ
                        3
                      
                      ⁢
                      I
                    
                  
                  )
                
                
                  -
                  1
                
              
              ⁡
              
                [
                
                  
                    
                      μ
                      2
                    
                    ⁡
                    
                      (
                      
                        
                          F
                          H
                        
                        ⁡
                        
                          (
                          
                            y
                            +
                            
                              u
                              k
                            
                            +
                            
                              b
                              u
                              k
                            
                          
                          )
                        
                      
                      )
                    
                  
                  +
                  
                    
                      μ
                      3
                    
                    ⁡
                    
                      (
                      
                        
                          Sx
                          
                            k
                            +
                            1
                          
                        
                        +
                        
                          b
                          v
                          k
                        
                      
                      )
                    
                  
                
                ]
              
            
          
          ,
          
            

          
          ⁢
          
            
          
          ⁢
          
            
              and
              ⁢
              
                

              
              ⁢
              
                
              
              ⁢
              
                u
                
                  k
                  +
                  1
                
              
            
            =
            
              
                
                  shrink
                  ⁡
                  
                    (
                    
                      
                        
                          Fv
                          
                            k
                            +
                            1
                          
                        
                        -
                        y
                        -
                        
                          b
                          u
                          k
                        
                      
                      ,
                      ɛ
                    
                    )
                  
                
                ⁢
                
                  
                
                ⁢
                wherein
                ⁢
                
                  

                
                ⁢
                
                  
                
                ⁢
                
                  shrink
                  ⁡
                  
                    (
                    
                      x
                      ,
                      T
                    
                    )
                  
                
              
              =
              
                {
                
                  
                    
                      0
                    
                    
                      
                        
                          
                            if
                            ⁢
                            
                              
                            
                            ⁢
                            
                              
                              x
                              
                            
                          
                          ≤
                          T
                        
                        ,
                      
                    
                  
                  
                    
                      x
                    
                    
                      
                        
                          
                            if
                            ⁢
                            
                              
                            
                            ⁢
                            
                              
                              x
                              
                            
                          
                          >
                          T
                        
                        ,
                        ,
                      
                    
                  
                
              
            
          
        
      
    
  


wherein k is an iteration counter, μ1, μ2 and μ3 are parameters of an augmented Lagrangian function





  
    
      L
      ⁢
      
        (
        
          x
          ,
          z
          ,
          u
          ,
          v
          ,
          
            b
            z
          
          ,
          
            b
            u
          
          ,
          
            b
            v
          
        
        )
      
    
    =
    
      
        
          
          z
          
        
        1
      
      +
      
        
          S
          ɛ
        
        ⁡
        
          (
          u
          )
        
      
      +
      
        
          
            μ
            1
          
          2
        
        ⁢
        
          
            
            
              Wx
              -
              z
            
            
          
          2
          2
        
      
      +
      
        
          
            μ
            2
          
          2
        
        ⁢
        
          
            
            
              Fv
              -
              y
              -
              u
            
            
          
          2
          2
        
      
      +
      
        
          
            μ
            3
          
          2
        
        ⁢
        
          
            
            
              Sx
              -
              v
            
            
          
          2
          2
        
      
      +
      
        
          μ
          1
        
        ⁢
        
          〈
          
            
              b
              z
            
            ,
            
              Wx
              -
              z
            
          
          〉
        
      
      +
      
        
          μ
          2
        
        ⁢
        
          〈
          
            
              b
              u
            
            ,
            
              u
              -
              Fv
              +
              y
            
          
          〉
        
      
      +
      
        
          μ
          3
        
        ⁢
        
          〈
          
            
              b
              v
            
            ,
            
              Sx
              -
              v
            
          
          〉
        
      
    
  
  ,




and bz, bu and bv are dual variables of the augmented Lagrangian.

22. The computer readable program storage device of claim 21, the method further comprising updating the dual variables as


bzk+1=bzk+(Wxk+1−zk+1),



buk+1=buk+(uk+1−Fvk+1+y), and



bvk+1=bvk+(Sxk+1−vk+1).

23. The computer readable program storage device of claim 21, wherein ε≦∥y∥2.

24. The computer readable program storage device of claim 21, wherein μ1, μ2, and μ3 are set as μ1=μ3=0.1ρ and μ2=ρ wherein




  ρ
  =
  
    
      1
      
        
          0.01
          ⁢
          
            
              
              
                
                  WA
                  H
                
                ⁢
                y
              
              
            
            
              ∞
              ⁢
              
                
              
            
          
        
        ⁢
        
          
        
      
    
    .

25. The computer readable program storage device of claim 22, wherein xk, zk, vk, and uk, and dual variables bzk, buk, and bvk are initialized to zero.

26. The computer readable program storage device of claim 21, wherein xk, zk, vk and uk are updated until a relative difference between a current iteration estimate and a previous iteration estimate fall below a predefined threshold.