Adaptive Sampling Algorithm For Matrix Completion

In order to ensure the quality of transmission,network monitoring is essential in largescale network data flow.However,it is not feasible to measure the network performance between all transmission pairs.As a newly emerging sparsity representation technique,matrix completion allows the recovery of a low-rank matrix using only a small number of random samples.Existing schemes often fix the number of samples assuming the rank of the matrix is known,while the data features thus the matrix rank vary over time,is not taken into account the problem of the matrix rank change.In this paper,considering the matrix rank change,the effectiveness of matrix sampling location and how to accelerate sampling in large network are studied.The main work and innovation are as follows:1.A two-stage Coherence sampling scheme based on random sampling and sampling stopping conditions is designed to determine the effective sampling location in large-scale networks.In the process of data sampling,the Coherence value of the remaining unsampled position is calculated by using a small number of known random sampling data,and the possible sampling position in the next stage is determined.This scheme can accurately obtain the information contained in all possible sampling positions in the next stage,and improve the accuracy of sampling.Finally,the simulation and parameter performance analysis show that this scheme can effectively reduce the number of samples and save the cost of sampling,so it is feasible.2.To solve the problem of how to speed up the sampling speed in large-scale networks,a method based on accelerated singular value decomposition(SVD)is proposed to reduce the matrix dimension.By analyzing three kinds of data sets,Harvard226,PSim500 and Meridian500,the experimental results show that they all meet the requirement of low rank.In the sampling process of Coherence scheme,it is necessary to determine the sampling position by using the Coherence value until the sampling stop condition is satisfied.Due to the large scale of data and the long waiting time of iterative process,the efficiency of matrix recovery is greatly reduced.In order to accelerate matrix completion,to reduce the dimension of matrix is very important.Based on the characteristics of the three real data sets and the simulation results of our scheme,a high recovery rate can be achieved under the condition of dimensionality reduction.In summary,this paper is aim to how to sample less data and how to collect data at a faster speed,aiming at the problems of complex data structure,large sampling data and slow processing speed in large network,and the research scheme is suitable for network requirements in different fields.