The correlation structure among the sensor observa- tions is a significant characteristic of the wireless sensor network (WSN) which can be exploited to drastically enhance the overall network performance. This structure is usually expressed as a low-rank approximation of the correlation matrix, although, in many cases the correlation of the captured data is full- rank. Thus, the computation of the full-rank correlation matrix by centralizing all the measurements into one node, puts at risk the privacy of the WSN. To overcome this problem, we impose privacy-preserving restrictions, in order to constrain the cooperation among the nodes, and hence promote the privacy. To this end, the decentralized estimation of the network-wide corre- lation matrix is obtained via a novel adaptive matrix completion technique, where at each step, a rank-one completion problem is solved. Through simulation experiments it has been verified that proposed algorithm converges to the full rank correlation matrix. Moreover, the proposed algorithm exhibits significantly lower computational complexity than the conventional technique. I.