Electrical and Computer Engineering
menu MENU

Theory Seminar

Information (or inferential) limits and computational limits

Raj RaoUniversity of Michigan
SHARE:

Information (or inferential) limits and computational limits are the objects of intense study in theoretical signal processing (TSP) and theoretical computer science (TCS). They magically (or not-so-magically) coincide in Shannon communication theory. We discuss some new information limits arising from random matrix theory (RMT) that describe when it is possible to reliably learn or uncover low-rank signal matrices buried in noise. Might these also coincide with the type of computational limits studied in TCS? We provide empirical evidence that suggest that these traditionally TSP questions might have interesting TCS counterparts.

Sponsored by

EECS