The Experts below are selected from a list of 231 Experts worldwide ranked by ideXlab platform

Marc Vuffray - One of the best experts on this subject based on the ideXlab platform.

  • Approaching the Rate-Distortion Limit with Spatial Coupling, Belief Propagation, and Decimation
    IEEE Transactions on Information Theory, 2015
    Co-Authors: Vahid Aref, Nicolas Macris, Marc Vuffray
    Abstract:

    We investigate an encoding scheme for lossy compression of a binary symmetric source based on simple spatially coupled Low-Density Generator-Matrix codes. The degree of the check nodes is regular and the one of code-bits is Poisson distributed with an average depending on the compression rate. The performance of a low complexity Belief Propagation Guided Decimation algorithm is excellent. The algorithmic rate-Distortion curve approaches the optimal curve of the ensemble as the width of the coupling window grows. Moreover, as the check degree grows both curves approach the ultimate Shannon rate-Distortion Limit. The Belief Propagation Guided Decimation encoder is based on the posterior measure of a binary symmetric test-channel. This measure can be interpreted as a random Gibbs measure at a "temperature" directly related to the "noise level of the test-channel". We investigate the links between the algorithmic performance of the Belief Propagation Guided Decimation encoder and the phase diagram of this Gibbs measure. The phase diagram is investigated thanks to the cavity method of spin glass theory which predicts a number of phase transition thresholds. In particular the dynamical and condensation "phase transition temperatures" (equivalently test-channel noise thresholds) are computed. We observe that: (i) the dynamical temperature of the spatially coupled construction saturates towards the condensation temperature; (ii) for large degrees the condensation temperature approaches the temperature (i.e. noise level) related to the information theoretic Shannon test-channel noise parameter of rate-Distortion theory. This provides heuristic insight into the excellent performance of the Belief Propagation Guided Decimation algorithm. The paper contains an introduction to the cavity method.

  • Approaching the Rate-Distortion Limit With Spatial Coupling, Belief Propagation, and Decimation
    IEEE Transactions on Information Theory, 2015
    Co-Authors: Vahid Aref, Nicolas Macris, Marc Vuffray
    Abstract:

    We investigate an encoding scheme for lossy compression of a binary symmetric source based on simple spatially coupled low-density generator-matrix codes. The degree of the check nodes is regular and the one of code-bits is Poisson distributed with an average depending on the compression rate. The performance of a low complexity belief propagation guided decimation algorithm is excellent. The algorithmic rate-Distortion curve approaches the optimal curve of the ensemble as the width of the coupling window grows. Moreover, as the check degree grows both curves approach the ultimate Shannon rate-Distortion Limit. The belief propagation guided decimation encoder is based on the posterior measure of a binary symmetric test-channel. This measure can be interpreted as a random Gibbs measure at a temperature directly related to the noise level of the test-channel. We investigate the links between the algorithmic performance of the belief propagation guided decimation encoder and the phase diagram of this Gibbs measure. The phase diagram is investigated thanks to the cavity method of spin glass theory which predicts a number of phase transition thresholds. In particular, the dynamical and condensation phase transition temperatures (equivalently test-channel noise thresholds) are computed. We observe that: 1) the dynamical temperature of the spatially coupled construction saturates toward the condensation temperature and 2) for large degrees the condensation temperature approaches the temperature (i.e., noise level) related to the information theoretic Shannon test-channel noise parameter of rate-Distortion theory. This provides heuristic insight into the excellent performance of the belief propagation guided decimation algorithm. This paper contains an introduction to the cavity method.

  • Approaching the rate-Distortion Limit by spatial coupling with belief propagation and decimation
    2013 IEEE International Symposium on Information Theory, 2013
    Co-Authors: Vahid Aref, Nicolas Macris, Marc Vuffray
    Abstract:

    We investigate an encoding scheme for lossy compression based on spatially coupled Low-Density GeneratorMatrix codes. The degree distributions are regular, or are Poisson on the code-bit side and check-regular which allows use for any compression rate. The performance of a low complexity Belief Propagation Guided Decimation algorithm is excellent, and for large check degrees it gets close to Shannon's rate-Distortion Limit. We investigate links between the algorithmic performance and the phase diagram of a relevant random Gibbs measure. The associated dynamical and condensation thresholds are computed within the framework of the cavity method. We observe that: (i) the dynamical threshold of the spatially coupled construction saturates towards the condensation threshold; (ii) for large degrees the condensation threshold approaches the information theoretic test-channel parameter of rate-Distortion theory. This provides heuristic insight into the excellent performance of the BPGD algorithm.

  • ISIT - Approaching the rate-Distortion Limit by spatial coupling with belief propagation and decimation
    2013 IEEE International Symposium on Information Theory, 2013
    Co-Authors: Vahid Aref, Nicolas Macris, Marc Vuffray
    Abstract:

    We investigate an encoding scheme for lossy compression based on spatially coupled Low-Density GeneratorMatrix codes. The degree distributions are regular, or are Poisson on the code-bit side and check-regular which allows use for any compression rate. The performance of a low complexity Belief Propagation Guided Decimation algorithm is excellent, and for large check degrees it gets close to Shannon's rate-Distortion Limit. We investigate links between the algorithmic performance and the phase diagram of a relevant random Gibbs measure. The associated dynamical and condensation thresholds are computed within the framework of the cavity method. We observe that: (i) the dynamical threshold of the spatially coupled construction saturates towards the condensation threshold; (ii) for large degrees the condensation threshold approaches the information theoretic test-channel parameter of rate-Distortion theory. This provides heuristic insight into the excellent performance of the BPGD algorithm.

Vahid Aref - One of the best experts on this subject based on the ideXlab platform.

  • Approaching the Rate-Distortion Limit with Spatial Coupling, Belief Propagation, and Decimation
    IEEE Transactions on Information Theory, 2015
    Co-Authors: Vahid Aref, Nicolas Macris, Marc Vuffray
    Abstract:

    We investigate an encoding scheme for lossy compression of a binary symmetric source based on simple spatially coupled Low-Density Generator-Matrix codes. The degree of the check nodes is regular and the one of code-bits is Poisson distributed with an average depending on the compression rate. The performance of a low complexity Belief Propagation Guided Decimation algorithm is excellent. The algorithmic rate-Distortion curve approaches the optimal curve of the ensemble as the width of the coupling window grows. Moreover, as the check degree grows both curves approach the ultimate Shannon rate-Distortion Limit. The Belief Propagation Guided Decimation encoder is based on the posterior measure of a binary symmetric test-channel. This measure can be interpreted as a random Gibbs measure at a "temperature" directly related to the "noise level of the test-channel". We investigate the links between the algorithmic performance of the Belief Propagation Guided Decimation encoder and the phase diagram of this Gibbs measure. The phase diagram is investigated thanks to the cavity method of spin glass theory which predicts a number of phase transition thresholds. In particular the dynamical and condensation "phase transition temperatures" (equivalently test-channel noise thresholds) are computed. We observe that: (i) the dynamical temperature of the spatially coupled construction saturates towards the condensation temperature; (ii) for large degrees the condensation temperature approaches the temperature (i.e. noise level) related to the information theoretic Shannon test-channel noise parameter of rate-Distortion theory. This provides heuristic insight into the excellent performance of the Belief Propagation Guided Decimation algorithm. The paper contains an introduction to the cavity method.

  • Approaching the Rate-Distortion Limit With Spatial Coupling, Belief Propagation, and Decimation
    IEEE Transactions on Information Theory, 2015
    Co-Authors: Vahid Aref, Nicolas Macris, Marc Vuffray
    Abstract:

    We investigate an encoding scheme for lossy compression of a binary symmetric source based on simple spatially coupled low-density generator-matrix codes. The degree of the check nodes is regular and the one of code-bits is Poisson distributed with an average depending on the compression rate. The performance of a low complexity belief propagation guided decimation algorithm is excellent. The algorithmic rate-Distortion curve approaches the optimal curve of the ensemble as the width of the coupling window grows. Moreover, as the check degree grows both curves approach the ultimate Shannon rate-Distortion Limit. The belief propagation guided decimation encoder is based on the posterior measure of a binary symmetric test-channel. This measure can be interpreted as a random Gibbs measure at a temperature directly related to the noise level of the test-channel. We investigate the links between the algorithmic performance of the belief propagation guided decimation encoder and the phase diagram of this Gibbs measure. The phase diagram is investigated thanks to the cavity method of spin glass theory which predicts a number of phase transition thresholds. In particular, the dynamical and condensation phase transition temperatures (equivalently test-channel noise thresholds) are computed. We observe that: 1) the dynamical temperature of the spatially coupled construction saturates toward the condensation temperature and 2) for large degrees the condensation temperature approaches the temperature (i.e., noise level) related to the information theoretic Shannon test-channel noise parameter of rate-Distortion theory. This provides heuristic insight into the excellent performance of the belief propagation guided decimation algorithm. This paper contains an introduction to the cavity method.

  • Approaching the rate-Distortion Limit by spatial coupling with belief propagation and decimation
    2013 IEEE International Symposium on Information Theory, 2013
    Co-Authors: Vahid Aref, Nicolas Macris, Marc Vuffray
    Abstract:

    We investigate an encoding scheme for lossy compression based on spatially coupled Low-Density GeneratorMatrix codes. The degree distributions are regular, or are Poisson on the code-bit side and check-regular which allows use for any compression rate. The performance of a low complexity Belief Propagation Guided Decimation algorithm is excellent, and for large check degrees it gets close to Shannon's rate-Distortion Limit. We investigate links between the algorithmic performance and the phase diagram of a relevant random Gibbs measure. The associated dynamical and condensation thresholds are computed within the framework of the cavity method. We observe that: (i) the dynamical threshold of the spatially coupled construction saturates towards the condensation threshold; (ii) for large degrees the condensation threshold approaches the information theoretic test-channel parameter of rate-Distortion theory. This provides heuristic insight into the excellent performance of the BPGD algorithm.

  • ISIT - Approaching the rate-Distortion Limit by spatial coupling with belief propagation and decimation
    2013 IEEE International Symposium on Information Theory, 2013
    Co-Authors: Vahid Aref, Nicolas Macris, Marc Vuffray
    Abstract:

    We investigate an encoding scheme for lossy compression based on spatially coupled Low-Density GeneratorMatrix codes. The degree distributions are regular, or are Poisson on the code-bit side and check-regular which allows use for any compression rate. The performance of a low complexity Belief Propagation Guided Decimation algorithm is excellent, and for large check degrees it gets close to Shannon's rate-Distortion Limit. We investigate links between the algorithmic performance and the phase diagram of a relevant random Gibbs measure. The associated dynamical and condensation thresholds are computed within the framework of the cavity method. We observe that: (i) the dynamical threshold of the spatially coupled construction saturates towards the condensation threshold; (ii) for large degrees the condensation threshold approaches the information theoretic test-channel parameter of rate-Distortion theory. This provides heuristic insight into the excellent performance of the BPGD algorithm.

David G. M. Mitchell - One of the best experts on this subject based on the ideXlab platform.

  • ISITA - On the windowed encoding complexity of SC-LDGM codes for lossy source compression
    2016
    Co-Authors: Ahmad Golmohammadi, Jörg Kliewer, Daniel J. Costello, David G. M. Mitchell
    Abstract:

    It has been shown that spatially coupled low-density generator-matrix (SC-LDGM) code ensembles display Distortion saturation for the lossy binary symmetric source coding problem with belief propagation guided decimation algorithms, in the sense that the Distortion of the SC-LDGM code ensemble approaches the optimal Distortion of the underlying (uncoupled) LDGM block code ensemble. This has also been demonstrated for the class of protograph-based SC-LDGM code ensembles with windowed encoding (WE), where Distortion close to the rate Distortion Limit was obtained with low-latency encoding. In this paper, we propose and compare two decimation techniques for lowering the WE complexity of SC-LDGM codes that maintain Distortion performance close to the rate-Distortion bound.

  • Windowed encoding of spatially coupled LDGM codes for lossy source compression
    2016 IEEE International Symposium on Information Theory (ISIT), 2016
    Co-Authors: Ahmad Golmohammadi, Jörg Kliewer, David G. M. Mitchell, Daniel J. Costello
    Abstract:

    Recently, it has been shown that a class of spatially coupled low-density generator-matrix (SC-LDGM) code ensembles displays Distortion saturation for the lossy binary symmetric source coding problem with the belief propagation guided decimation (BPGD) algorithm, i.e., the BPGD Distortion approaches the optimal expected Distortion of the underlying ensemble asymptotically in code length. Here, we investigate the Distortion performance of a practical class of protograph-based SC-LDGM code ensembles and demonstrate Distortion saturation numerically. Moreover, we propose an efficient windowed encoding (WE) algorithm that takes advantage of the convolutional structure of the SC-LDGM codes. By using the WE algorithm, a Distortion very close to the rate-Distortion Limit can be achieved for a fixed compression rate with low-to-moderate encoding latency.

  • On the windowed encoding complexity of SC-LDGM codes for lossy source compression
    2016 International Symposium on Information Theory and Its Applications (ISITA), 2016
    Co-Authors: Ahmad Golmohammadi, Jörg Kliewer, Daniel J. Costello, David G. M. Mitchell
    Abstract:

    It has been shown that spatially coupled low-density generator-matrix (SC-LDGM) code ensembles display Distortion saturation for the lossy binary symmetric source coding problem with belief propagation guided decimation algorithms, in the sense that the Distortion of the SC-LDGM code ensemble approaches the optimal Distortion of the underlying (uncoupled) LDGM block code ensemble. This has also been demonstrated for the class of protograph-based SC-LDGM code ensembles with windowed encoding (WE), where Distortion close to the rate Distortion Limit was obtained with low-latency encoding. In this paper, we propose and compare two decimation techniques for lowering the WE complexity of SC-LDGM codes that maintain Distortion performance close to the rate-Distortion bound.

Nicolas Macris - One of the best experts on this subject based on the ideXlab platform.

  • Approaching the Rate-Distortion Limit with Spatial Coupling, Belief Propagation, and Decimation
    IEEE Transactions on Information Theory, 2015
    Co-Authors: Vahid Aref, Nicolas Macris, Marc Vuffray
    Abstract:

    We investigate an encoding scheme for lossy compression of a binary symmetric source based on simple spatially coupled Low-Density Generator-Matrix codes. The degree of the check nodes is regular and the one of code-bits is Poisson distributed with an average depending on the compression rate. The performance of a low complexity Belief Propagation Guided Decimation algorithm is excellent. The algorithmic rate-Distortion curve approaches the optimal curve of the ensemble as the width of the coupling window grows. Moreover, as the check degree grows both curves approach the ultimate Shannon rate-Distortion Limit. The Belief Propagation Guided Decimation encoder is based on the posterior measure of a binary symmetric test-channel. This measure can be interpreted as a random Gibbs measure at a "temperature" directly related to the "noise level of the test-channel". We investigate the links between the algorithmic performance of the Belief Propagation Guided Decimation encoder and the phase diagram of this Gibbs measure. The phase diagram is investigated thanks to the cavity method of spin glass theory which predicts a number of phase transition thresholds. In particular the dynamical and condensation "phase transition temperatures" (equivalently test-channel noise thresholds) are computed. We observe that: (i) the dynamical temperature of the spatially coupled construction saturates towards the condensation temperature; (ii) for large degrees the condensation temperature approaches the temperature (i.e. noise level) related to the information theoretic Shannon test-channel noise parameter of rate-Distortion theory. This provides heuristic insight into the excellent performance of the Belief Propagation Guided Decimation algorithm. The paper contains an introduction to the cavity method.

  • Approaching the Rate-Distortion Limit With Spatial Coupling, Belief Propagation, and Decimation
    IEEE Transactions on Information Theory, 2015
    Co-Authors: Vahid Aref, Nicolas Macris, Marc Vuffray
    Abstract:

    We investigate an encoding scheme for lossy compression of a binary symmetric source based on simple spatially coupled low-density generator-matrix codes. The degree of the check nodes is regular and the one of code-bits is Poisson distributed with an average depending on the compression rate. The performance of a low complexity belief propagation guided decimation algorithm is excellent. The algorithmic rate-Distortion curve approaches the optimal curve of the ensemble as the width of the coupling window grows. Moreover, as the check degree grows both curves approach the ultimate Shannon rate-Distortion Limit. The belief propagation guided decimation encoder is based on the posterior measure of a binary symmetric test-channel. This measure can be interpreted as a random Gibbs measure at a temperature directly related to the noise level of the test-channel. We investigate the links between the algorithmic performance of the belief propagation guided decimation encoder and the phase diagram of this Gibbs measure. The phase diagram is investigated thanks to the cavity method of spin glass theory which predicts a number of phase transition thresholds. In particular, the dynamical and condensation phase transition temperatures (equivalently test-channel noise thresholds) are computed. We observe that: 1) the dynamical temperature of the spatially coupled construction saturates toward the condensation temperature and 2) for large degrees the condensation temperature approaches the temperature (i.e., noise level) related to the information theoretic Shannon test-channel noise parameter of rate-Distortion theory. This provides heuristic insight into the excellent performance of the belief propagation guided decimation algorithm. This paper contains an introduction to the cavity method.

  • Approaching the rate-Distortion Limit by spatial coupling with belief propagation and decimation
    2013 IEEE International Symposium on Information Theory, 2013
    Co-Authors: Vahid Aref, Nicolas Macris, Marc Vuffray
    Abstract:

    We investigate an encoding scheme for lossy compression based on spatially coupled Low-Density GeneratorMatrix codes. The degree distributions are regular, or are Poisson on the code-bit side and check-regular which allows use for any compression rate. The performance of a low complexity Belief Propagation Guided Decimation algorithm is excellent, and for large check degrees it gets close to Shannon's rate-Distortion Limit. We investigate links between the algorithmic performance and the phase diagram of a relevant random Gibbs measure. The associated dynamical and condensation thresholds are computed within the framework of the cavity method. We observe that: (i) the dynamical threshold of the spatially coupled construction saturates towards the condensation threshold; (ii) for large degrees the condensation threshold approaches the information theoretic test-channel parameter of rate-Distortion theory. This provides heuristic insight into the excellent performance of the BPGD algorithm.

  • ISIT - Approaching the rate-Distortion Limit by spatial coupling with belief propagation and decimation
    2013 IEEE International Symposium on Information Theory, 2013
    Co-Authors: Vahid Aref, Nicolas Macris, Marc Vuffray
    Abstract:

    We investigate an encoding scheme for lossy compression based on spatially coupled Low-Density GeneratorMatrix codes. The degree distributions are regular, or are Poisson on the code-bit side and check-regular which allows use for any compression rate. The performance of a low complexity Belief Propagation Guided Decimation algorithm is excellent, and for large check degrees it gets close to Shannon's rate-Distortion Limit. We investigate links between the algorithmic performance and the phase diagram of a relevant random Gibbs measure. The associated dynamical and condensation thresholds are computed within the framework of the cavity method. We observe that: (i) the dynamical threshold of the spatially coupled construction saturates towards the condensation threshold; (ii) for large degrees the condensation threshold approaches the information theoretic test-channel parameter of rate-Distortion theory. This provides heuristic insight into the excellent performance of the BPGD algorithm.

Daniel J. Costello - One of the best experts on this subject based on the ideXlab platform.

  • ISITA - On the windowed encoding complexity of SC-LDGM codes for lossy source compression
    2016
    Co-Authors: Ahmad Golmohammadi, Jörg Kliewer, Daniel J. Costello, David G. M. Mitchell
    Abstract:

    It has been shown that spatially coupled low-density generator-matrix (SC-LDGM) code ensembles display Distortion saturation for the lossy binary symmetric source coding problem with belief propagation guided decimation algorithms, in the sense that the Distortion of the SC-LDGM code ensemble approaches the optimal Distortion of the underlying (uncoupled) LDGM block code ensemble. This has also been demonstrated for the class of protograph-based SC-LDGM code ensembles with windowed encoding (WE), where Distortion close to the rate Distortion Limit was obtained with low-latency encoding. In this paper, we propose and compare two decimation techniques for lowering the WE complexity of SC-LDGM codes that maintain Distortion performance close to the rate-Distortion bound.

  • Windowed encoding of spatially coupled LDGM codes for lossy source compression
    2016 IEEE International Symposium on Information Theory (ISIT), 2016
    Co-Authors: Ahmad Golmohammadi, Jörg Kliewer, David G. M. Mitchell, Daniel J. Costello
    Abstract:

    Recently, it has been shown that a class of spatially coupled low-density generator-matrix (SC-LDGM) code ensembles displays Distortion saturation for the lossy binary symmetric source coding problem with the belief propagation guided decimation (BPGD) algorithm, i.e., the BPGD Distortion approaches the optimal expected Distortion of the underlying ensemble asymptotically in code length. Here, we investigate the Distortion performance of a practical class of protograph-based SC-LDGM code ensembles and demonstrate Distortion saturation numerically. Moreover, we propose an efficient windowed encoding (WE) algorithm that takes advantage of the convolutional structure of the SC-LDGM codes. By using the WE algorithm, a Distortion very close to the rate-Distortion Limit can be achieved for a fixed compression rate with low-to-moderate encoding latency.

  • On the windowed encoding complexity of SC-LDGM codes for lossy source compression
    2016 International Symposium on Information Theory and Its Applications (ISITA), 2016
    Co-Authors: Ahmad Golmohammadi, Jörg Kliewer, Daniel J. Costello, David G. M. Mitchell
    Abstract:

    It has been shown that spatially coupled low-density generator-matrix (SC-LDGM) code ensembles display Distortion saturation for the lossy binary symmetric source coding problem with belief propagation guided decimation algorithms, in the sense that the Distortion of the SC-LDGM code ensemble approaches the optimal Distortion of the underlying (uncoupled) LDGM block code ensemble. This has also been demonstrated for the class of protograph-based SC-LDGM code ensembles with windowed encoding (WE), where Distortion close to the rate Distortion Limit was obtained with low-latency encoding. In this paper, we propose and compare two decimation techniques for lowering the WE complexity of SC-LDGM codes that maintain Distortion performance close to the rate-Distortion bound.