Characterizing complex quantum systems is a vital task in quantum information science. Quantum tomography, the standard tool used for this purpose, uses a well-designed measurement record to reconstruct quantum states and processes. It is, however, notoriously inefficient. Recently, the classical signal reconstruction technique known as “compressed sensing” has been ported to quantum information science to overcome this challenge: accurate tomography can be achieved with substantially fewer measurement settings, thereby greatly enhancing the efficiency of quantum tomography. Here we show that compressed sensing tomography of quantum systems is essentially guaranteed by a special property of quantum mechanics itself—that the mathematical objects that describe the system in quantum mechanics are matrices with nonnegative eigenvalues. This result has an impact on the way quantum tomography is understood and implemented. In particular, it implies that the information obtained about a quantum system through compressed sensing methods exhibits a new sense of “informational completeness.” This has important consequences on the efficiency of data taking for quantum tomography, and enables us to construct informationally complete measurements that are robust to noise and modeling errors. Moreover, our result shows that one can expand the numerical tool-box used in quantum tomography and employ highly efficient algorithms developed to handle large dimensional matrices on a large dimensional Hilbert space. While we mainly present our results in the context of quantum tomography, they apply to the general case of positive semidefinite matrix recovery.