Recommender systems are algorithms that suggest content or products to users on the internet. These are becoming ever more important due to the massive growth of content on popular web sites, yet their design is often only guided by empirical results. This has two drawbacks: mathematical analysis lags behind the use of the methods, and the methods may focus too much on immediate results instead of taking a wider perspective, leading to unintended consequences such as social media polarization. To help offset those drawbacks, this thesis considers both how one may analyze recommender systems more rigorously, as well as how they may be improved by optimizing not just for short-term results. The thesis approaches recommender systems from a compressed sensing perspective, starting with an explanation of compressed sensing as the study of how to approximate the cardinality minimization problem. It then proceeds to give a review of how compressed sensing can be generalized to approximate two matrix-valued problems, called matrix sensing and matrix completion. The application of matrix completion to the bilinear factorization model used in recommender systems follows, and we finish by investigating improvements to the basic bilinear factorization model, as well as suggesting other directions of improvement.