An Overview of Moving Object Trajectory Compression Algorithms <s> Compressive Sensing. <s> Suppose x is an unknown vector in Ropfm (a digital image or signal); we plan to measure n general linear functionals of x and then reconstruct. If x is known to be compressible by transform coding with a known transform, and we reconstruct via the nonlinear procedure defined here, the number of measurements n can be dramatically smaller than the size m. Thus, certain natural classes of images with m pixels need only n=O(m1/4log5/2(m)) nonadaptive nonpixel samples for faithful recovery, as opposed to the usual m pixel samples. More specifically, suppose x has a sparse representation in some orthonormal basis (e.g., wavelet, Fourier) or tight frame (e.g., curvelet, Gabor)-so the coefficients belong to an lscrp ball for 0<ples1. The N most important coefficients in that expansion allow reconstruction with lscr2 error O(N1/2-1p/). It is possible to design n=O(Nlog(m)) nonadaptive measurements allowing reconstruction with accuracy comparable to that attainable with direct knowledge of the N most important coefficients. Moreover, a good approximation to those N important coefficients is extracted from the n measurements by solving a linear program-Basis Pursuit in signal processing. The nonadaptive measurements have the character of "random" linear combinations of basis/frame elements. Our results use the notions of optimal recovery, of n-widths, and information-based complexity. We estimate the Gel'fand n-widths of lscrp balls in high-dimensional Euclidean space in the case 0<ples1, and give a criterion identifying near- optimal subspaces for Gel'fand n-widths. We show that "most" subspaces are near-optimal, and show that convex optimization (Basis Pursuit) is a near-optimal way to extract information derived from these near-optimal subspaces <s> BIB001 </s> An Overview of Moving Object Trajectory Compression Algorithms <s> Compressive Sensing. <s> Some mobile sensor network applications require the sensor nodes to transfer their trajectories to a data sink. This paper proposes an adaptive trajectory (lossy) compression algorithm based on compressive sensing. The algorithm has two innovative elements. First, we propose a method to compute a deterministic projection matrix from a learnt dictionary. Second, we propose a method for the mobile nodes to adaptively predict the number of projections needed based on the speed of the mobile nodes. Extensive evaluation of the proposed algorithm using 6 datasets shows that our proposed algorithm can achieve sub-metre accuracy. In addition, our method of computing projection matrices outperforms two existing methods. Finally, comparison of our algorithm against a state-of-the-art trajectory compression algorithm show that our algorithm can reduce the error by 10-60 cm for the same compression ratio. <s> BIB002
Compressive sensing (CS) is an efficient signal processing technique to acquire and reconstruct a signal by finding solutions to underdetermined linear systems. It is also known as compressed sensing, compressive sampling, or sparse sampling. CS is with the principle that, through optimization, the sparsity of a signal can be exploited to recovery from far fewer samples than required by the Shannon-Nyquist sampling theorem. There are two conditions under which recovery is possible. The first one is sparsity which requires the signal to be sparse in some domain. The second one is incoherence which is applied through the isometric property which is sufficient for sparse signals BIB001 . In this section, we will discuss CS given in literature BIB002 briefly. Given a vector ∈ R , the representation ∈ R can be computed on a basis ∈ R × by solving the linear equation = which is said to be compressible if has a large number of elements with small magnitude. If there is a basis on which a given vector has a compressible representation, then is also compressible. Compressive sensing considers the problem of recovering an unknown compressible vector from its projections. Let Φ be an × projection matrix with < . Consider the equation where ∈ R is a noise vector whose norm is bounded by . Compressive sensing aims to reconstruct from and Φ given the knowledge that is compressible on the basis . Compressive sensing shows that under certain conditions it is possible to recover by solving the following ℓ 1 optimization problem: Given̂, can be estimated from̂=̂. In the context of trajectory compression, is the trajectory measured by a Mobile Sensor Networks node. The dimension of is large. The MSN node computes = Φ and transmits to the server. The server can compute an estimated trajectorŷby using , Φ, and to solve the aforementioned ℓ 1 optimization problem as shown in  . Note that the compression is lossy with 1 − / representing both space savings and reduction in wireless transmission requirement.