Information (or inferential) limits and computational limits

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.