We present a new least squares based diamond scheme for anisotropic diffusion problems on polygonal meshes. This scheme introduces both cell-centered unknowns and vertexunknowns. The vertex unknowns are intermediate ones and are expressed aslinear combinations with the surrounding cell-centeredunknowns by a new vertex interpolation algorithm which is alsoderived in least squares approach. The least squares approach is very flexible due to that theleast squares method can solve overdetermined linear system. Both of the new scheme and the vertex interpolation algorithmare applicable to diffusion problems with discontinuous andanisotropic diffusion tensor on polygonal meshes. Besides, they are linearity-preserving under givenassumptions, and the optimal converge rates for both L2 errorand H1 error are observed in numerical experiments. More interesting is that a very robust performance of the newvertex interpolation algorithm on random meshes compared withthe algorithm LPEW2 can be found from the numerical tests.