We address the problem of reconstructing scalar and vector functions from non-uniform data. The reconstruction problem is formulated as a minimization problem where the cost is a weighted sum of two terms. The first data term is the quadratic measure of goodness of fit, whereas the second regularization term is a smoothness functional. We concentrate on the case where the later is a semi-norm involving differential operators. We are interested in a solution that is invariant with respect to scaling and rotation of the input data. We first show that this is achieved whenever the smoothness functional is both scale- and rotation-invariant. In the first part of the thesis, we address the scalar problem. An elegant solution having the above mentioned invariant properties is provided by Duchon's method of thin-plate splines. Unfortunately, the solution involves radial basis functions that are poorly conditioned and becomes impractical when the number of samples is large. We propose a computationally efficient alternative where the minimization is carried out within the space of uniform B-splines. We show how the B-spline coefficients of the solution can be obtained by solving a well-conditioned, sparse linear system of equations. By taking advantage of the refinable nature of B-splines, we devise a fast multiresolution-multigrid algorithm. We demonstrate the effectiveness of this method in the context of image processing. Next, we consider the reconstruction of vector functions from projected samples, meaning that the input data do not contain the full vector values, but only some directional components. We first define the rotational invariance and the scale invariance of a vector smoothness functional, and then characterize the complete family of such functionals. We show that such a functional is composed of a weighted sum of two sub-functionals: (i) Duchon's scalar semi-norm applied on the divergence field; (ii) and the same applied to each component of the rotational field. This forms a three-parameter family, where the first two are the Duchon's order of the above sub-functionals, and the third is their relative weight. Our family is general enough to include all vector spline formulations that have been proposed so far. We provide the analytical solution for this minimization problem and show that the solution can be expressed as a weighted sum of vector basis functions, which we call the generalized vector splines. We construct the linear system of equations that yields the required weights. As in the scalar case, we also provide an alternative B-spline solution for this problem, and propose a fast multigrid algorithm. Finally, we apply our vector field reconstruction method to cardiac motion field recovery from ultrasound pulsed wave Doppler data, and demonstrate its clinical potential.