Search

Publication in the conference proceedings of SampTA, Bremen, Germany, 2013

We study a new technique for optimal data compression subject to conditions of causality and different types of memory. The technique is based on the assumption that some information about compressed data can be obtained from a solution of the associated problem without constraints of causality and memory. This allows us to consider two separate problem related to compression and decompression subject to those constraints. Their solutions are given and the analysis of the associated errors is provided., {"references":["I.T. Jolliffe, Principal Component Analysis, Springer Verlag, New York,\n1986.","Y. Hua and M. Nikpour, Computing the reduced rank Wiener filter by\nIQMD, IEEE Signal Processing Letters, No. 9, Vol. 6, pp. 240-242, 1999.","L. L. Scharf, The SVD and reduced rank signal processing, Signal\nProcessing, vol. 25, 113 - 133, 1991.","Y. Hua and W. Q. Liu, Generalized Karhunen-Lo`eve transform, IEEE\nSignal Processing Letters, vol. 5, pp. 141-143, 1998.","A. Torokhti and P. Howlett, Computational Methods for Modelling of\nNonlinear Systems, Elsevier, 2007.","A. Torokhti, P. Howlett, IEEE Trans. Circuits & Syst., II, Analog & Digit.\nSignal Processing, 48, 2001.","S. Friedland, A. Niknejad, M. Kaveh, H. Zare, Fast Monte-Carlo low\nrank approximations for matrices, 10 pp. submited.","T. Zhang, G. Golub, Rank-One Approximation to High Order Tensors,\nSIAM J. Matrix Anal. Appl., 23, 2001.","P. Common, G.H. Golub, Tracking a few extreme singular values and\nvectors in signal processing, Proc. IEEE, 78, 1990.\n[10] E. D. Sontag, Lecture Notes in Control and Information Sciences, 13\n1979.\n[11] R. M. De Santis, Causality Theory in Systems Analysis, Proc. of IEEE,\n64, pp. 36-44, 1976.\n[12] G. H. Golub and C. F. Van Loan, Matrix Computations, Baltimore, MD:\nJohns Hopkins University Press, 1996.\n[13] A. Ben-Israel and T. N. E. Greville, Generalized Inverses: Theory and\nApplications, John Wiley & Sons, New York, 1974.\n[14] V. Gimeno, Obtaining the EEG envelope in real time: a practical method\nbased on homomorphic filtering, Neuropsychobiology, 18, (1987) pp 110-\n112.\n[15] H. Kim, G.H. Golub, H. Park, Missing value estimation for DNA\nmicroarray gene expression data: local least squares imputation, Bioinformatics,\n21, 2005."]}

Refereed/Peer-reviewed Many recent applications involve distributed signal processing where a source signal is observed by, say, local receiver-transmitters and then transmitted to a reconstruction center for the signal estimation. An optimal determination of the receiver-transmitters and the reconstruction center requires extensions of the Karhunen-Loève transform (KLT) and Wiener filter. In this paper, the associated extensions are provided. The proposed optimal multilinear filter is a generalization of the Wiener filter and consists of terms where each term is associated with a local receiver-transmitter. For the case when the receiver-transmitters must reduce the dimensionality of the observed signals, two associated techniques are proposed: the multilinear KLT-1 and multilinear KLT-2. The multilinear KLT-1 is constructed in terms of pseudo-inverse matrices and therefore always exists. The multilinear KLT-2 is given in terms of non-singular matrices and it may provide a higher associated accuracy than that of the multilinear KLT-1. All three proposed techniques are based on a reduction of the original problem to separate error minimization problems with small matrices. This allows us to provide a fast computational procedure for the multilinear filter, and decrease the computational cost for constructing the multilinear KLT-1 and KLT-2. IEEE

We propose and justify a new approach to constructing optimal nonlinear transforms of random vectors. We show that the proposed transform improves such characteristics of rank-reduced transforms as compression ratio, accuracy of decompression and reduces required computational work. The proposed transform ${\mathcal T}_p$ is presented in the form of a sum with $p$ terms where each term is interpreted as a particular rank-reduced transform. Moreover, terms in ${\mathcal T}_p$ are represented as a combination of three operations ${\mathcal F}_k$, ${\mathcal Q}_k$ and ${\boldsymbol{\phi}}_k$ with $k=1,...,p$. The prime idea is to determine ${\mathcal F}_k$ separately, for each $k=1,...,p$, from an associated rank-constrained minimization problem similar to that used in the Karhunen--Lo\`{e}ve transform. The operations ${\mathcal Q}_k$ and ${\boldsymbol{\phi}}_k$ are auxiliary for finding ${\mathcal F}_k$. The contribution of each term in ${\mathcal T}_p$ improves the entire transform performance. A corresponding unconstrained nonlinear optimal transform is also considered. Such a transform is important in its own right because it is treated as an optimal filter without signal compression. A rigorous analysis of errors associated with the proposed transforms is given., Comment: Published in SIGMA (Symmetry, Integrability and Geometry: Methods and Applications) at http://www.emis.de/journals/SIGMA/

Our work addresses an improvement in accuracy for dimensionality reduction and reconstruction of random signals. The proposed transform targets noisy signals. This is because in the case of highly noisy signals, the known optimal methods might produce a large associated error. Let x, y and u be a source signal with m components, observed noisy signal with n components and reduced signal with k components, respectively, and let c = k / min { m , n } be a reduction ratio (RR) where k ≤ min {m, n}. If RR is fixed then the error associated with the known methods cannot be improved. The purpose of this paper is the development of an approach which leads to the better performance than that of the well-known fundamental techniques. The associated accuracy is improved by an optimal choice of an “auxiliary” random signal v (called the injection) and its dimensionality q, and by the increase in the number of matrices to optimize compared to the known transforms. At the same time, the total number of entries of the matrices is less than for the known related transforms. The proposed method contains, in particular, a special operation Q which transforms the large covariance matrix to the block diagonal form with smaller blocks. The above circumstances make the proposed technique numerically faster than the known related transforms. Numerical examples are provided that illustrate the above advantages.

Let $\boldsymbol{f}$ be a square-integrable, zero-mean, random vector with observable realizations in a Hilbert space H, and let $\boldsymbol{g}$ be an associated square-integrable, zero-mean, random vector with realizations which are not observable in a Hilbert space K. We seek an optimal filter in the form of a closed linear operator X acting on the observable realizations of a proximate vector $\boldsymbol{f}_{\epsilon } \approx \boldsymbol{f}$ that provides the best estimate $\widehat{\boldsymbol{g}}_{\epsilon} = X \boldsymbol{f}_{\epsilon}$ of the vector $\boldsymbol{g}$ . We assume the required covariance operators are known. The results are illustrated with a typical example.

New multi-objective operators of random signals are presented in this paper. The new operators improve, under a unrestrictive condition, the performance of known techniques: the generalized Karhunen-Loéve transform, the transform considered by Brillinger and the generalized Brillinger-like transform. This is obtained by particular design of new operators which have more parameters to optimize than that of other operators described in literature. Refereed/Peer-reviewed

We develop an extension of the Karhunen-Loeve transform (KLT) that provides better associated accuracy than that of the original KLT and its known generalizations. It is achieved via a special structure of the proposed transform which contains more parameters to optimize than those in the known transforms. Its specific feature is an auxiliary signal w used to improve the transform performance. In particular, the associated transform accuracy improves if the dimension of w increases. Refereed/Peer-reviewed

We propose novel transforms of stochastic vectors, called the generalized Brillinger transforms (GBT1 and GBT2), which are generalizations of the Brillinger transform (BT). The GBT1 extends the BT to the cases when the covariance matrix and the weighting matrix are singular, and moreover, the weighting matrix is not necessarily symmetric. We show that the GBT1 may computationally be preferable over another related optimal technique, the generic Karhunen-Loève transform (GKLT). The GBT2 generalizes the GBT1 to provide, under the condition we impose, better associated accuracy than that of the GBT1. It is achieved because of the increase in a number of parameters to optimize compared to that in the GBT1. Refereed/Peer-reviewed

In this paper, a new theory of optimal weighted nonlinear filtering is presented. Two filter models are considered. The first model is based on a representation of the filter in the polynomial-like form with q terms where each term consists of weighted matrices and the matrix determined from the error minimization problem. The second model extends the first one to the case of the filter concatenation. The filter models are given in terms of pseudo-inverse matrices, i.e., the requirement of invertibility for covariance matrices is omitted. Thus, our filters always exist. We develop methods which allow us to exploit advantages associated with the proposed nonlinear filter models. The methods consist of the orthogonalization procedure and the reduction of the original problem to q individual minimization problems for smaller matrices. This leads to a considerable reduction in the required computational work. The error associated with the first filter model decreases when the number q of terms of filter increases. Its compression ratio can be adjusted by varying a particular value of ranks in each of its q terms. This means that the proposed filer structure provides the two degrees of freedom. The second filter model provides another degree of freedom, a number k of filters in the concatenation. Variations of the degrees of freedom improve the performance of the proposed filters. In particular, the error associated with the filter concatenation decreases as the filter number k in the concatenation increases. Refereed/Peer-reviewed

A new technique is provided for random vector estimation from noisy data under the constraints that the estimator is causal and dependent on at most a finite number p of observations. Nonlinear estimators defined by multilinear operators of degree r are employed, the choice of r allowing a trade-off between the accuracy of the optimal filter and the complexity of the calculations. The techniques utilise an exact correspondence of the nonlinear problem to a corresponding linear one. This is then solved by a new procedure, the least squares singular pivot algorithm, whereby the linear problem can be repeated reduced to smaller structurally similar problems. Invertibility of the relevant covariance matrices is not assumed. Numerical experiments with real data are used to illustrate the efficacy of the new algorithm.

This paper concerns the best causal operator approximation of the identity mapping subject to a specified variable finite memory constraint. The causality and memory constraints require that the approximating operator takes the form of a lower stepped matrix A. To find the best such matrix, we propose a new technique based on a block-partition into an equivalent collection of smaller blocks, {L"0,K"1,L"1,...,K"@?,L"@?} where each L"r is a lower triangular block and each K"r is a rectangular block and where @? is known. The sizes of the individual blocks are defined by the memory constraints. We show that the best approximation problem for the lower stepped matrix A can be replaced by an equivalent collection of @? independent best approximation problems in terms of the matrices [L"0],[K"1,L"1],...,[K"@?,L"@?]. The solution to each individual problem is found and a representation of the overall solution and associated error is given.

In this paper, a new approach to constructing optimal nonlinear transforms of random vectors is proposed and justified. The proposed transform T/sub p/ is presented in the form of a sum with p terms where each term is interpreted as a particular rank-reduced transform. Moreover, terms in T/sub p/ are represented as a combination of three operations F/sub k/, Q/sub k/, and /spl psi//sub k/ with k=1,...,p. The prime idea is to determine F/sub k/ separately, for each k=1,...,p, from an associated rank-constrained minimization problem similar to that used in the Karhunen-Loe/spl grave/ve transform (KLT). The operations Q/sub k/ and /spl psi//sub k/ are auxiliary for finding F/sub k/. The contribution of each term in T/sub p/ improves the entire transform performance. A rigorous analysis of errors associated with the proposed transforms is given. It is shown that the proposed transform improves such characteristics of rank-reduced transforms as compression ratio and the accuracy of decompression and reduces required computational work. The Fourier series in Hilbert space, the Wiener filter, the KLT and the transforms presented in earlier author papers in the field are particular cases of the proposed method. Theoretical results are illustrated with numerical simulations.

We propose a new method for the optimal causal representation of nonlinear systems. The proposed approach is based on the best constrained approximation of mappings in probability spaces by operators constructed from matrices of special form so that the approximant preserves the causality property. It is supposed that the observable input is contaminated with noise. The approximant minimises the mean-square difference between a desired output signal and the output signal of the approximating model. The method provides a numerically realisable mathematical model of the system. An analysis is given of the error associated with this representation.

We propose a new approach which generalizes and improves principal component analysis (PCA) and its recent advances. The approach is based on the following underlying ideas. PCA can be reformulated as a technique which provides the best linear estimator of the fixed rank for random vectors. By the proposed method, the vector estimate is presented in a special quadratic form aimed to improve the error of estimation compared with customary linear estimates. The vector is first pre-estimated from the special iterative procedure such that each iterative loop consists of a solution of the unconstrained nonlinear best approximation problem. Then, the final vector estimate is obtained from a solution of the constrained best approximation problem with the quadratic approximant. We show that the combination of these techniques allows us to provide a new nonlinear estimator with a significantly better performance compared with that of PCA and its known modifications.

Let u be a random signal with realisations in an infinite-dimensional vector space X and υ an associated observable random signal with realisations in a finite-dimensional subspace Y ⊆ X. We seek a pointwise-best estimate of u using a bounded linear filter on the observed data vector υ. When x is a finite-dimensional Euclidean space and the covariance matrix for υ is nonsingular, it is known that the best estimate û of u is given by a standard matrix expression prescribing a linear mean-square filter. For the infinite-dimensional Hilbert space problem we show that the matrix expression must be replaced by an analogous but more general expression using bounded linear operators. The extension procedure depends directly on the theory of the Bochner integral and on the construction of appropriate HilbertSchmidt operators. An extended example is given.

Suppose KY and KX are large sets of observed and reference signals, respectively, each containing N signals. Is it possible to construct a filter F : KY → KX that requires a priori information only on few signals, p N, from KX but performs better than the known filters based on a priori information on every reference signal from KX? It is shown that the positive answer is achievable under quite unrestrictive assumptions. The device behind the proposed method is based on a special extension of the piecewise linear interpolation technique to the case of random signal sets. The proposed technique provides a single filter to process any signal from the arbitrarily large signal set. The filter is determined in terms of pseudo-inverse matrices so that it always exists., {"references":["H. Kopka and P. W. Daly, A Guide to LATEX, 3rd ed. Harlow, England:\nAddison-Wesley, 1999.","J. Chen, J. Benesty, Y. Huang, and S. Doclo, New Insights Into the Noise\nReduction Wiener Filter, IEEE Trans. on Audio, Speech, and Language Processing, 14, No. 4, pp. 1218 - 1234, 2006.","M. Spurbeck and P. Schreier, Causal Wiener filter banks for periodically\ncorrelated time series, Signal Processing, 87, 6, pp. 1179-1187, 2007.","J. S. Goldstein, I. Reed, and L. L. Scharf, \"A Multistage Representation\nof the Wiener Filter Based on Orthogonal Projections,\" IEEE Trans. on Information Theory, vol. 44, pp. 2943-2959, 1998.","Y. Hua, M. Nikpour, and P. Stoica, \"Optimal Reduced-Rank estimation\nand filtering,\" IEEE Trans. on Signal Processing, vol. 49, pp. 457-469, 2001.","A. Torokhti and P. Howlett, Computational Methods for Modelling of Nonlinear Systems, Elsevier, 2007.","E. D. Sontag, Polynomial Response Maps, Lecture Notes in Control and\nInformation Sciences, 13, 1979.","S. Chen and S. A. Billings, Representation of non-linear systems: NARMAX model, Int. J. Control, vol. 49, no. 3, pp. 1013-1032, 1989.","V. J. Mathews and G. L. Sicuranza, Polynomial Signal Processing, J.\nWiley & Sons, 2001.\n[10] A. Torokhti and P. Howlett, Optimal Transform Formed by a Combination\nof Nonlinear Operators: The Case of Data Dimensionality Reduction, IEEE Trans. on Signal Processing, 54, No. 4, pp. 1431-1444, 2006.\n[11] A. Torokhti and P. Howlett, Filtering and Compression for Infinite Sets\nof Stochastic Signals, Signal Processing, 89, pp. 291-304, 2009.\n[12] J. Vesma and T. Saramaki, Polynomial-Based Interpolation Filters - Part\nI: Filter Synthesis, Circuits, Systems, and Signal Processing, Volume 26,\nNumber 2, Pages 115-146, 2007.\n[13] A. Torokhti and J. Manton, Generic Weighted Filtering of Stochastic\nSignals, IEEE Trans. on Signal Processing, 57, issue 12, pp. 4675-4685,\n2009.\n[14] A. Torokhti and S. Miklavcic, Data Compression under Constraints of\nCausality and Variable Finite Memory, Signal Processing, 90 , Issue 10, pp. 2822-2834, 2010.\n[15] I. Babuska, U. Banerjee, J. E. Osborn, Generalized finite element\nmethods: main ideas, results, and perspective, International Journal of Computational Methods, 1 (1), pp. 67-103, 2004.\n[16] S. Kang and L. Chua, A global representation of multidimensional\npiecewise-linear functions with linear partitions, IEEE Trans. on Circuits\nand Systems, 25 Issue:11, pp. 938 - 940, 1978.\n[17] L.O. Chua and A.-C. Deng, Canonical piecewise-linear representation,\nIEEE Trans. on Circuits and Systems, 35 Issue:1, pp. 101-111, 1988.\n[18] J.-N. Lin and R. Unbehauen, Adaptive nonlinear digital filter with canonical piecewise-linear structure, IEEE Trans. on Circuits and Systems, 37\nIssue:3, pp. 347 - 353, 1990.\n[19] J.-N. Lin and R. Unbehauen, Canonical piecewise-linear approximations,\nIEEE Trans. on Circuits and Systems I: Fundamental Theory and Applications,\n39 Issue:8, pp. 697 - 699, 1992.\n[20] S.B. Gelfand and C.S. Ravishankar, A tree-structured piecewise linear\nadaptive filter, IEEE Trans. on Inf. Theory, 39, issue 6, pp. 1907-1922,\n1993.\n[21] E.A. Heredia and G.R. Arce, Piecewise linear system modeling based on\na continuous threshold decomposition, IEEE Trans. on Signal Processing,\n44 Issue:6, pp. 1440 - 1453, 1996.\n[22] G. Feng, Robust filtering design of piecewise discrete time linear\nsystems, IEEE Trans. on Signal Processing, 53 Issue:2, pp. 599 - 605,2005.\n[23] F. Russo, Technique for image denoising based on adaptive piecewise\nlinear filters and automatic parameter tuning, IEEE Trans. on Instrumentation\nand Measurement, 55, Issue:4, pp. 1362 - 1367, 2006.\n[24] J.E. Cousseau, J.L. Figueroa, S. Werner, T.I. Laakso, Efficient Nonlinear\nWiener Model Identification Using a Complex-Valued Simplicial Canonical\nPiecewise Linear Filter, IEEE Trans. on Signal Processing, 55 Issue:5, pp. 1780 - 1792, 2007.\n[25] P. Julian, A. Desages, B. D-Amico, Orthonormal high-level canonical\nPWL functions with applications to model reduction, IEEE Trans. on\nCircuits and Systems I: Fundamental Theory and Applications, 47 Issue:5,\npp. 702 - 712, 2000.\n[26] T. Wigren, Recursive Prediction Error Identification Using the Nonlinear\nWiener Model, Automatica, 29, 4, pp. 1011-1025, 1993.\n[27] G. H. Golub and C. F. van Loan, Matrix Computations, Johns Hopkins\nUniversity Press, Baltimore, 1996.\n[28] T. Anderson, An Introduction to Multivariate Statistical Analysis, New\nYork, Wiley, 1984.\n[29] L. I. Perlovsky and T. L. Marzetta, Estimating a Covariance Matrix\nfrom Incomplete Realizations of a Random Vector, IEEE Trans. on Signal\nProcessing, 40, pp. 2097-2100, 1992.\n[30] O. Ledoit and M. Wolf, A well-conditioned estimator for largedimensional\ncovariance matrices, J. Multivariate Analysis 88, pp. 365-411, 2004."]}

Wireless sensor networks involve a set of sp

In this paper we give an explicit solution to the rank constrained matrix approximation in Frobenius norm, which is a generalization of the classical approximation of an m by n matrix A by a matrix of rank k at most., Comment: 4 pages

A nonlinear dynamical system is modelled as a nonlinear mapping from a set of input signals into a corresponding set of output signals. Each signal is specified by a set of real number parameters, but such sets may be uncountably infinite. For numerical simulation of the system each signal must be represented by a finite parameter set and the mapping must be defined by a finite arithmetical process. Nevertheless the numerical simulation should be a good approximation to the mathematical model. We discuss the representation of realistic dynamical systems and establish a stable approximation theorem for numerical simulation of such systems. First published in Proceedings of the American Mathematical Society in vol. 132, no. 2 (2004), published by the American Mathematical Society