Performing PCA with only a distance matrix I want to cluster a massive dataset for which I have only the pairwise distances. I implemented a k-medoids algorithm, but it's taking too long to run so I would like to start by reducing the dimension of my problem by applying PCA. However, the only way I know to perform this method is using the covariance matrix which I don't have in my situation.
Is there a way to apply PCA knowing the pairwise distances only?
 A: PCA with a distance matrix exists, and it is called Multi-dimensional scaling (MDS). You can learn more on wikipedia or in this book.
You can do it in R with mds function cmdscale. For a sample x, you can check that prcomp(x) and cmdscale(dist(x)) give the same result (where prcomp does PCA and dist just computes euclidian distances between elements of x)
A: This looks like a problem that spectral clustering could be applied to. Since you have the pairwise distance matrix, you can define a fully connected graph where each node has N connections, corresponding to its distance from every other node in the graph. From this, you can compute the graph Laplacian (if this sounds scary, don't worry--it's an easy computation) and then take eigenvectors of the smallest eigenvalues (this is where it differs from PCA). If you take 3 eigenvectors, for example, you will then have an Nx3 matrix. In this space, the points should (hopefully) be well-separated because of some neat graph theory which suggests that this is an optimal cut for maximizing flow (or distance, in this case) between clusters. From there, you could use a k-means or similar algorithm to cluster in 3-space. I recommend checking out this awesome walkthrough for more insight:
http://arxiv.org/abs/0711.0189
A: Update: I entirely removed my original answer, because it was based on a confusion between Euclidean distances and scalar products. This is a new version of my answer. Apologies.
If by pairwise distances you mean Euclidean distances, then yes, there is a way to perform PCA and to find principal components. I describe the algorithm in my answer to the following question: What's the difference between principal components analysis and multidimensional scaling?
Very briefly, the matrix of Euclidean distances can be converted into a centered Gram matrix, which can be directly used to perform PCA via eigendecomposition. This procedure is known as [classical] multidimensional scaling (MDS).
If your pairwise distances are not Euclidean, then you cannot perform PCA, but still can perform MDS, which is not going to be equivalent to PCA anymore. However, in this situation MDS is likely to be even better for your purposes.
A: The pairwise distances also form a square matrix just like the co-variance matrix.  PCA is just SVD (http://en.wikipedia.org/wiki/Singular_value_decomposition) applied to the co-variance matrix. You should still be able to do dimension reduction using SVD on your data.  I'm not exactly sure how to interpret your output but it is definitely something to try.  You could use clustering methods such as k-means or hierarchical clustering.  Also take a look at other dimension reduction techniques such as multidimensional scaling.  What are you trying to get out of your clusters?  
