Due to geological conditions, acquisition environment, and economic restrictions, acquired seismic data are often incomplete and irregularly distributed, and this affects subsequent migration imaging and inversion. Sparse constraint-based methods are widely used for seismic data interpolation, including fixed-base transform and dictionary learning. Fixed-base transform methods are fast and simple to implement, but the basis function needs to be pre-selected. The dictionary learning method is more adaptive, and provides a means of learning the sparse representation from corrupted data. K-singular value decomposition (K-SVD) is a classical dictionary learning method that combines sparse coding and dictionary updating iteratively. However, the dictionary atoms are updated column-by-column, leading to high computational complexity due to long SVD calculation times. In this study, we evaluated the dictionary learning method via l4-norm maximisation using an orthogonal dictionary, which is different from the traditional l0-norm or l1-norm minimisation, and interpolated the missing traces in the projection onto convex sets (POCS) framework. The optimal objection function is convex, but can be solved using a simple and efficient Matching, Stretching and Projection (MSP) algorithm, which greatly reduces the dictionary learning time. Numerical experiments using synthetic and field data demonstrate the effectiveness of the proposed method.