Columbia Technology Ventures

Guaranteed optimization with loopy belief propagation

Many important applied problems require finding the most likely configuration of a system, also known as maximum likelihood estimation and, more generally, maximum a posteriori (MAP) estimation. This technology proposes a conversion of the Bayesian network into a nand random field. It characterizes when decoding (such as turbo codes) is guaranteed exact and allows extensions to the coding schemes that do not violate exactness of the decoding and encoding procedures. This invention increases the decoding capabilities of widely used error correcting codes such as turbo codes and LPDC codes used in 3G wireless telephony networks and in satellite communications. It is also applicable to image processing problems and search.

Guaranteed optimality, exactness, and efficiency improves information transfer

While turbo codes and LDPC codes may approach the Shannon limit of information transfer, it is often difficult to verify their optimality. With this technology, exact decoding is possible and guaranteed if the underlying network can be converted into a perfect graph. This technology thus increases the decoding capabilities of widely used error correcting codes and may be applied to fields such as 3G wireless standards, satellite communications, and internet search.

This technology has been tested with computational modeling.

Lead Inventor:

Tony Jebara, Ph.D.

Applications:

  • Communication systems such as 3G mobile telephony standards, NASA missions, and satellite communications
  • Image decoding
  • Speeding up image searching in search engines
  • Terrestrial mobile television systems
  • Wireless metropolitan network standards

Advantages:

  • Guaranteed exactness, optimality, and efficiency
  • Extendable schemes
  • Broad applications

Patent information:

Patent Pending (US 20110040619)

Tech Ventures Reference: IR M09-093

Related Publications: