Technologies are presented for anomaly detection in a cloud environment using a sparsity measure. In some examples, cloud metric data may be gathered and processed into a dictionary base. Linear transform coefficients for a test sample may then be calculated from the dictionary base using l1-norm minimization. A sparsity measure may then be computed from the linear transform coefficients. If the sparsity measure does not exceed a predefined threshold, the test sample may be determined as anomalous.