It is essential to improve intra prediction performance to raise the efficiency of video coding. In video coding standards such as H.265/HEVC, intra prediction is seen as an extension of directional prediction schemes, examples include refinement of directions, planar extension, filtering reference sampling, and so on. From the view point of reducing prediction error, some improvements on intra prediction for standardized schemes have been suggested. However, on the assumption that the correlation between neighboring pixels are static, these conventional methods use pre-defined predictors regardless of the image being encoded. Therefore, these conventional methods cannot reduce prediction error if the images break the assumption made in prediction design. On the other hand, adaptive predictors that change the image being encoded may offer poor coding efficiency due to the overhead of the additional information needed for adaptivity. This paper proposes an adaptive intra prediction scheme that resolves the trade-off between prediction error and adaptivity overhead. The proposed scheme is formulated as a constrained optimization problem that minimizes prediction error under sparsity constraints on the prediction coefficients. In order to solve this problem, a novel solver is introduced as an extension of LARS for multi-class support. Experiments show that the proposed scheme can reduce the amount of encoded bits by 1.21% to 3.24% on average compared to HM16.7.