The main promise of compressed sensing is the accurate recovery of high-dimensional structured signals from an underdetermined set of randomized linear projections. Several types of structure have been explored in the literature such as sparsity and low-rankness. Recent results provide a characterization of the abstract meaning of "structure" and also develop universal compressed
sensing algorithms. Such schemes are able to recover any structured signal from enough number of random projections. However, the proposed algorithms are based on Kolmogorov complexity, and hence are impractical. In this talk, I will present new results that pave the road for building efficient universal compressed sensing algorithms.