Phase diagram and approximate message passing for blind calibration and dictionary learning

Author

Krzakala, Florent ; Mezard, Marc ; Zdeborova, Lenka

Author_Institution

ESPCI, Paris, France

fYear

2013

fDate

7-12 July 2013

Firstpage

659

Lastpage

663

Abstract

We consider dictionary learning and blind calibration for signals and matrices created from a random ensemble. We study the mean-squared error in the limit of large signal dimension using the replica method and unveil the appearance of phase transitions delimiting impossible, possible-but-hard and possible inference regions. We also introduce an approximate message passing algorithm that asymptotically matches the theoretical performance, and show through numerical tests that it performs very well, for the calibration problem, for tractable system sizes.

Keywords

calibration; inference mechanisms; learning (artificial intelligence); matrix algebra; mean square error methods; message passing; random processes; approximate message passing algorithm; blind calibration; calibration problem; dictionary learning; large signal dimension; matrices; mean-squared error; numerical test; phase diagram; phase transitions delimiting; possible inference region; possible-but-hard region; random ensemble; replica method; tractable system size; Approximation methods; Calibration; Compressed sensing; Dictionaries; Information theory; Message passing; Sparse matrices;

fLanguage

English

Publisher

ieee

Conference_Titel

Information Theory Proceedings (ISIT), 2013 IEEE International Symposium on

Conference_Location

Istanbul

ISSN

2157-8095

Type

conf

DOI

10.1109/ISIT.2013.6620308

Filename

6620308