This limitation is circumvented by using scalable and non–memory–intensive harmonic expansions. In this paper, the projection of parametric surfaces onto disk and spherical harmonics bases is investigated, and three novel computationally efficient algorithms are proposed based on the randomised Kaczmarz (RK). To boost the computational performance and convergence of the root mean square error (RMSE) of the reconstructed surfaces we exploited the conjugate symmetry property of the harmonic basis functions. Further, the sparsity of the signals is used for estimating the projection coefficients from an undersampled surface. The first algorithm only takes into consideration the conjugate symmetry property for enhancing the convergence of the RMSE. The second algorithm endows the sparse version of the RK algorithm with the conjugate symmetry property. The third algorithm combines the previous two to further accelerate the convergence of the RMSE. The performance of the developed algorithms is tested on three surfaces where we demonstrate that they outperform conventional reconstruction techniques in terms of processing time with comparable precision.