Mesh deformation methods [8] have been widely used for the past decades in various fields such as fluid-structure interaction, aerodynamic shape optimization, unsteady and aeroelastic computational fluid dynamics. Such methods are particularly interesting in order to update meshes during a simulation without the need to perform an (often expensive) full regeneration of the mesh, e.g. when facing moving boundaries or geometry update during a structural optimization loop. Among the numerous existing methods, radial basis functions interpolation (RBF) [1] is particularly suitable for unstructured mesh applications due to its simplicity and the high quality of the resulting mesh. One key aspect of RBF-based mesh deformation is the resolution of a dense linear system, which tends to be computationally expensive and high memory demanding when dealing with large-scale meshes [2, 3], thus being a major drawback of the method. This could be mitigated using an iterative solver instead of a direct one during the resolution step, thus saving the memory needed to store the factorization. However, some radial basis functions lead to ill-conditioned systems, requiring the use of an efficient preconditioner which tends to complexify the problem. In this work, we aim to speed-up the resolution of this linear system using alternative randomization techniques coming from probabilistic linear algebra to solve the as-sociated dense linear system. Indeed, such methods have been studied for two decades and are being increasingly popular in various fields, including numerical linear algebra and optimization [5]. Their key aspect is to reduce the complexity of solving large scale linear systems by exploiting the spectral properties of the underlying operator. In this study, we propose an alternative approach for dealing with the input matrix by generating an approximate ”sketch” of the initial problem. This sketch is easier to solve compared to working with the original matrix directly, albeit at the expense of reduced precision. Our focus lies specifically on matrices arising from RBF-based mesh deformation procedures, which typically exhibit a rapid spectral decay and tend to be numerically low rank. Leveraging these characteristics, we explore the potential of probabilistic linear algebra techniques in this domain. To embed the rows of the linear system into a lower-dimensional space while preserving their geometric properties, we employ a dimension reduction map. By doing so, we maintain the underlying geometry of the original space, thereby ensuring that the approximated sketch exhibits similar behavior in terms of singular values and singular vectors as the original matrix. Our chosen method for constructing this map involves utilizing highly structured random matrices, commonly referred to as randomized linear embeddings or random projections. Subsequently, we confine the matrix to the approximated subspace and compute a standard factorization of the reduced matrix. The proposed approach will be discussed on the basis of 2D and 3D applications.