Orthogonal AMP
Approximate message passing (AMP) is a low-cost iterative signal recovery algorithm for linear system models. When the system transform matrix has independent identically distributed (IID) Gaussian entries, the performance of AMP can be asymptotically characterized by a simple scalar recursion calle...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2017-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/7817805/ |
| _version_ | 1819163189849358336 |
|---|---|
| author | Junjie Ma Li Ping |
| author_facet | Junjie Ma Li Ping |
| author_sort | Junjie Ma |
| collection | DOAJ |
| description | Approximate message passing (AMP) is a low-cost iterative signal recovery algorithm for linear system models. When the system transform matrix has independent identically distributed (IID) Gaussian entries, the performance of AMP can be asymptotically characterized by a simple scalar recursion called state evolution (SE). However, SE may become unreliable for other matrix ensembles, especially for ill-conditioned ones. This imposes limits on the applications of AMP. In this paper, we propose an orthogonal AMP (OAMP) algorithm based on de-correlated linear estimation (LE) and divergence-free non-linear estimation (NLE). The Onsager term in standard AMP vanishes as a result of the divergence-free constraint on NLE. We develop an SE procedure for OAMP and show numerically that the SE for OAMP is accurate for general unitarily-invariant matrices, including IID Gaussian matrices and partial orthogonal matrices. We further derive optimized options for OAMP and show that the corresponding SE fixed point coincides with the optimal performance obtained via the replica method. Our numerical results demonstrate that OAMP can be advantageous over AMP, especially for ill-conditioned matrices. |
| first_indexed | 2024-12-22T17:40:11Z |
| format | Article |
| id | doaj.art-5fda340669e44b6283893cb5085ab8e2 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-22T17:40:11Z |
| publishDate | 2017-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-5fda340669e44b6283893cb5085ab8e22022-12-21T18:18:26ZengIEEEIEEE Access2169-35362017-01-0152020203310.1109/ACCESS.2017.26531197817805Orthogonal AMPJunjie Ma0https://orcid.org/0000-0003-1263-5006Li Ping1Department of Statistics, Columbia University, New York, NY, USADepartment of Electronic Engineering, City University of Hong Kong, Hong KongApproximate message passing (AMP) is a low-cost iterative signal recovery algorithm for linear system models. When the system transform matrix has independent identically distributed (IID) Gaussian entries, the performance of AMP can be asymptotically characterized by a simple scalar recursion called state evolution (SE). However, SE may become unreliable for other matrix ensembles, especially for ill-conditioned ones. This imposes limits on the applications of AMP. In this paper, we propose an orthogonal AMP (OAMP) algorithm based on de-correlated linear estimation (LE) and divergence-free non-linear estimation (NLE). The Onsager term in standard AMP vanishes as a result of the divergence-free constraint on NLE. We develop an SE procedure for OAMP and show numerically that the SE for OAMP is accurate for general unitarily-invariant matrices, including IID Gaussian matrices and partial orthogonal matrices. We further derive optimized options for OAMP and show that the corresponding SE fixed point coincides with the optimal performance obtained via the replica method. Our numerical results demonstrate that OAMP can be advantageous over AMP, especially for ill-conditioned matrices.https://ieeexplore.ieee.org/document/7817805/Compressed sensingapproximate message passing (AMP)replica methodstate evolutionunitarily-invariantIID Gaussian |
| spellingShingle | Junjie Ma Li Ping Orthogonal AMP IEEE Access Compressed sensing approximate message passing (AMP) replica method state evolution unitarily-invariant IID Gaussian |
| title | Orthogonal AMP |
| title_full | Orthogonal AMP |
| title_fullStr | Orthogonal AMP |
| title_full_unstemmed | Orthogonal AMP |
| title_short | Orthogonal AMP |
| title_sort | orthogonal amp |
| topic | Compressed sensing approximate message passing (AMP) replica method state evolution unitarily-invariant IID Gaussian |
| url | https://ieeexplore.ieee.org/document/7817805/ |
| work_keys_str_mv | AT junjiema orthogonalamp AT liping orthogonalamp |