Several Data Flow Reconstruction Method Based On Compressed Sensing

A lot of online and continuously updating data streams with high rate need to be dealt with in such systems as internet management system, telecommunication system, securities trading system and financial trading system. In consequence, uninterrupted data processing without delay is essential for systems with limited storage space. In addition, large amounts of structural information are also included in the data stream apart from data information, which may lead to high data dimension and therefore impose great pressure on network transmission. Hence, effective stream data processing methods are extremely needed, and the reconstruction of stream data is one of the hot issues in the field of data compression.The Compressed Sensing (CS) theory is adopted to gather a merely small amount of observational data with "picky and particular" requirements, from which we can restore the original signal with certain optimal approaches. Accordingly, the CS theory provides a new way to solve the problem of data stream compression. In this thesis, three data compression algorithms as well as their differences are presented, in which CS theory is combined with Belief Propagation (BP) and information transfer algorithm during data stream compression reconstruction process.The concrete research work of this thesis is arranged as follows:First, an improved local coding and decoding algorithm are proposed. The algorithms can read or modify compressed data without decompression via transmitting information in counter chain, which simplify the process of data reading and modifying. But the local decoding and encoding algorithm are complex because it use every counters related in the decoding process. The function of the status bit is considered in the improved local decoding and encoding algorithm, which can lead to a better decoding result through updating the sparse graph, and can improve greatly the utility rate of storage space and reduce the access complexity as well.Secondly, a multi-layer CS-BP decoding algorithm in sparse graph structure is presented. As the decoding algorithm of LDPC codes, BP algorithm makes full use of the decoding method of channel information, which can improve greatly the decoding performance. To combine the merits of the sampling information of a small amount with the advantages of BP decoding algorithm, CS-BP algorithm can reduce both the time and space complexity of the compressed sensing process. Moreover, when multi-layer CS-BP algorithm is applied to the counter chain structure, advantages of the counter chain multi-layer storage will be combined excellently, which can result in a better reconstruction data flow results with less storage space occupied.Thirdly, the weighted L1/2regularization algorithm is proposed finally. In the process of compression and reconstruction, the regular subsemigroups of l1/2norm can produce a sparser solution than l1norm. Therefore, L1/2regularization method is adopted as a preferential method to address problems in data stream compression process. However, large coefficients in original signal play a more important role for the algorithm recovery. To solve the problem above and balance the effect of all the coefficients to the optimal solution, weighted L1/2regularization method has been put to use for reconstructing the data flow with an improved performance, which makes a smaller correct solution norm compared with other solutions so that the correct solution can be detected more easily.