1. A method for detecting anomalies in cloud monitoring, the method comprising: collecting training samples from a plurality of metrics associated with operations of a cloud based entity; forming a dictionary from the training samples; determining linear transform coefficients for a test sample using the dictionary; determining a sparsity measure of the linear transform coefficients for the test sample; and in response to a determination that the sparsity measure is below a predefined threshold, classifying the test sample as an anomaly.