The emerging cloud computing technologies enable a cloud platform to provide diverse cloud services to its service subscribers. By federating different services within and across cloud boundaries, cloud service developers can provision new, composite cloud services in the marketplace of apps and services on a cloud platform. Complete and accurate service QoS information is important for service recommendation and service pricing. However, measuring the entire QoS matrix for all user-service pairs incurs a tremendous overhead and is practically infeasible. This work designs efficient algorithms for recovering the complete QoS matrix from partial measurements, exploiting the low rank feature of the matrix. Our solution applies tools from differential geometry for transforming rank-constrained matrix optimization in a flat space into an unconstrained geometric optimization in a smooth manifold. Besides QoS matrix completion, future QoS matrix prediction based on manifold algorithms is also studied in this work, for the first time in the literature.