In this paper we propose two sets of compressed learning methods. First, for the setting where the matrix that is used to compress the signal is known, then for the setting where the matrix is unknown. With a known measurement matrix, compressed learning can benefit from the success of compressed sensing by utilizing the intermediate results of signal recovery. In particular, we use a compressed sensing algorithm Blocked Successive Regression (BSR) to generate enhanced features, then apply some widely used machine learning models (such as multilayer perceptron and convolutional neural network) on the enhanced features. It is observed that the machine learning results are significantly improved. With an unknown measurement matrix, deep models are developed to learn the matrix. We develop two compressed learning models based on the variational autoencoders (VAE) framework, reducing the problem of learning the elements of the matrix to learning the distributional parameters of the matrix. This method significantly reduces the number of parameters to learn, and also offers robustness to small perturbation in data.