If I understand your question properly, you should find a correlation matrix which is close, in some sense, to a given matrix which may have negative eigenvalues. This problem arises often on practice, and there are quite a few papers devoted to it. For example:
N.J. Higham, Computing the nearest correlation matrix - a problem from finance, IMA J. Numer. Anal. 22 (2002), 329-343
S. Boyd and L. Xiao, Least-squares covariance matrix adjustment, SIAM J. Matrix Anal. Appl. 27 (2005), N2, 532-546 http://www.stanford.edu/~boyd/papers/psd_cone_proj.html
as well as some other papers of Higham at http://www.maths.manchester.ac.uk/~higham/papers/ .
I should admit that I worked in a bank some years ago, and encountered this problem on "practice", while computing correlations between various so-called "financial instruments". In all situations I encountered, it was enough to use what is called the cutoff method in the arXiv paper you cite - i.e. zero out the (small) negative eigenvalues. The financial analysts around me considered this as a heavy-duty wizardy and were very pleased.
Best Answer
Check out How to calculate correlation accurately. There are two common formulas that are algebraically equivalent but one has much better numerical properties than the other.