Multivariable matrix spectral factorization

Abstract

A method for performing Multivariable Matrix Spectral Factorization has been developed, which allows factorization in real time high-dimensional matrices with multivariable high-order polynomial or non-rational entries. Systems implementing the method provide improved performance and capabilities in applications reducible to multivariable matrix spectral factorization.

Claims

1. A computer system comprising a receiver for receiving multidimensional information; one or more processors; and a non-transitory computer-readable medium operatively connected to the one or more processors and including computer code configured to: receive a signal input based upon n parameters, where n is greater than 1; apply n-D Matrix Spectral Factorization to the received signal input; and transmit an output of the n-D Matrix Spectral Factorization; and wherein the n-D Matrix Spectral Factorization is a multivariable matrix spectral factorization comprising: performing, for a given multivariable matrix spectral density, a lower-upper triangular factorization to factor the given multivariable matrix spectral density into a first matrix and a conjugate transpose of the first matrix, and recurrently processing the first matrix by preparing an auxiliary matrix considering a submatrix of the first matrix, expanding auxiliary entries of the auxiliary matrix into series with general coefficients, cutting the tails, constructing multivariable wavelet matrices, and increasing a dimension of the considered submatrix, and applying a canonical spectral factor to a result of the recurrent processing of the first matrix.

2. The system of claim 1, wherein the signal input is a complex signal input depending on several parameters.

3. The system of claim 1, wherein the signal input is a noisy signal of a wireless communication system.

4. The system of claim 1, wherein the output signal is a repaired version of the received signal from which noise has been removed.

5. The system of claim 1, wherein the multivariable matrix spectral factorization performs n-variable multidimensional filtering on the signal input.

6. The system of claim 1, wherein the multivariable matrix spectral factorization performs image or video compression on the signal input.

7. The system of claim 1, wherein the multivariable matrix spectral factorization is utilized with the multiparameter Granger causality test.

8. An apparatus, comprising: receiving means for receiving a signal input based upon n parameters, where n is greater than 1; processing means for applying n-D Matrix Factorization to the received signal input; and transmitting means for providing a signal output of the n-D Matrix Spectral Factorization; and wherein the n-D Matrix Spectral Factorization is a multivariable matrix spectral factorization comprising: performing, for a given multivariable matrix spectral density, a lower-upper triangular factorization to factor the given multivariable matrix spectral density into a first matrix and a conjugate transpose of the first matrix, and recurrently processing the first matrix by preparing an auxiliary matrix considering a submatrix of the first matrix, expanding auxiliary entries of the auxiliary matrix into series with general coefficients, cutting the tails, constructing multivariable wavelet matrices, and increasing a dimension of the considered submatrix, and applying a canonical spectral factor to a result of the recurrent processing of the first matrix.

9. The apparatus of claim 8, wherein the signal input is a noisy signal of a wireless communication system.

10. The apparatus of claim 8, wherein the signal input is a complex signal input depending on several parameters.

11. The apparatus of claim 8, wherein the output signal is a repaired version of the received signal from which noise has been removed.

12. The apparatus of claim 8, wherein the multivariable matrix spectral factorization performs n-variable multidimensional filtering on the signal input.

13. The apparatus of claim 8, wherein the multivariable matrix spectral factorization performs image or video compression on the signal input.

14. The apparatus of claim 8, wherein the multivariable matrix spectral factorization is utilized with the multiparameter Granger causality test.

15. A method executing on one or more processors, comprising: receiving a signal input based upon n parameters, where n is greater than 1; applying n-D Matrix Spectral Factorization to the received signal input by: performing, for a given multivariable matrix spectral density, a lower-upper triangular factorization to factor the given multivariable matrix spectral density into a first matrix and a conjugate transpose of the first matrix, recurrently processing the first matrix by preparing an auxiliary matrix considering a submatrix of the first matrix, expanding auxiliary entries into series with general coefficients, cutting the tails, constructing multivariable wavelet matrices, and increasing a dimension of the considered submatrix, and applying a canonical spectral factor to a result of the recurrent processing of the first matrix; and transmitting an output of the n-D Matrix Spectral Factorization.

16. The method of claim 15, wherein the signal input is a noisy signal of a wireless communication system.

17. The method of claim 15, wherein the signal input is a complex signal input depending on several parameters.

18. The method of claim 15, wherein the output signal is a repaired version of the received signal from which noise has been removed.

19. The method of claim 15, wherein the multivariable matrix spectral factorization performs n-variable multidimensional filtering on the signal input.

20. The method of claim 15, wherein the multivariable matrix spectral factorization performs image or video compression on the signal input.

Description

BRIEF DESCRIPTION OF DRAWINGS

(1) The foregoing and other features of the present disclosure will become more fully apparent from the following description and appended claims, taken in conjunction with the accompanying drawings. Understanding that these drawings depict only several implementations in accordance with the disclosure and are therefore, not to be considered limiting of its scope, the disclosure will be described with additional specificity and detail through use of the accompanying drawings.

(2) FIG. 1 illustrates a computer system for use with certain implementations.

(3) FIG. 2 illustrates a device according to an example implementation.

(4) FIG. 3 illustrates a method according to an example implementation.

(5) FIG. 4 illustrates a system according to an example implementation.

(6) FIG. 5 illustrates an apparatus according to an example implementation.

(7) FIG. 6 illustrates a method according to an example implementation.

(8) FIG. 7 illustrates an apparatus according to an example implementation.

(9) Reference is made to the accompanying drawings throughout the following detailed description. In the drawings, similar symbols typically identify similar components, unless context dictates otherwise. The illustrative implementations described in the detailed description, drawings, and claims are not meant to be limiting. Other implementations may be utilized, and other changes may be made, without departing from the spirit or scope of the subject matter presented here. It will be readily understood that the aspects of the present disclosure, as generally described herein, and illustrated in the figures, can be arranged, substituted, combined, and designed in a wide variety of different configurations, all of which are explicitly contemplated and made part of this disclosure.

DETAILED DESCRIPTION OF VARIOUS EMBODIMENTS

(10) Embodiments described herein relate generally to a Multivariable Matrix Spectral Factorization with applications including, but not limited to, n-Dimensional Filtering, Image and Video Compression, and Radar Systems. A new multivariate matrix spectral factorization (n-D MSF) method has been developed which has low computational complexity and can be implemented in real time. It can be used to factorize non-rational matrices as well. The proposed method is non-trivial and non-obvious generalization of the matrix spectral factorization (1-D MSF) method described in the Background section. Multivariable Matrix Spectral Factorization (n-D MSF) is used to process multidimensional data indexed with n parameters (e.g., color 2-D images, or 3-D tomographic images), while 1-D MSF deals with data indexed with a single parameter. The n-D MSF provides a mechanism for overcoming computational limitations with current hardware in order to solve complicated problems integral to various special purpose applications as mentioned above. The lack of efficient methods for such calculations has been considered to be a major bottleneck that makes many theoretical developments in multidimensional signals and systems infeasible.

(11) While the new n-D MSF method shares some general characteristic features of 1-D MSF method, it presents a solution to a long felt problem with prior factorization methods. The n-D MSF performs the spectral factorization of a multivariable matrix-function by step-by-step factorizing the left-upper submatrices of lower dimension. The accuracy of the result can be controlled at each step, which is crucial for the efficiency of the method. Specifically, the method comprises the following steps: 1. A lower-upper triangular factorization of the given multivariable matrix-function is performed along with corresponding scalar spectral factorizations on the main diagonal. 2. At each step mentioned above, a unitary multivariable matrix-function is found which converts a corresponding left-upper submatrix into the spectral factor by multiplication from the right. The special properties of this unitary multivariate matrix-function, the method for identifying it, and its role in the factorization process constitute the main ideas of the algorithm. This approach eliminates the technical difficulties of the problem that inhibited its efficient implementation until now. 3. The class of above mentioned unitary multivariable matrix functions plays important role in the theory of multivariable wavelets and multirate filter banks which can become an additional source of practical applications.

(12) A substantial difference from 1-D case is that n-D MSF method uses polynomials with coefficients from the field of rational functions of several complex variables instead of usual polynomials used in 1-D MSF method. This cannot be done with the current 1-D MSF method.

(13) Turning to the detailed mathematical description of the method, let S be a given rr matrix function of n complex variables z=(z.sub.1, z.sub.2, . . . , z.sub.n)

(14) $\begin{array}{cc}S\left(z\right)=\left(\begin{array}{cccc}{f}_{1,1}\left(z\right)& f_{1,2}\left(z\right)& \mathrm{.Math.}& f_{1,r}\left(z\right)\\ f_{2,1}\left(z\right)& f_{2,2}\left(z\right)& \mathrm{.Math.}& f_{2,r}\left(z\right)\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ f_{r,1}\left(z\right)& f_{r,2}\left(z\right)& \mathrm{.Math.}& f_{r,r}\left(z\right)\end{array}\right),z{\mathrm{��}}^n,& \left(1\right)\end{array}$
with integrable entries, .sub.ijL.sub.1 (.sup.n), having the Fourier expansion

(15) $\begin{array}{cc}S\left(z\right)=\underset{k=\left(k_1,k_2,\mathrm{.Math.},k_n\right){}^n}{.Math.}{C}_k{z}^k,C_k{}^{rr},z^k=z_1^{k_1}{z}_2^{k_2}\mathrm{.Math.}{z}_n^{k_n}.& \left(2\right)\end{array}$

(16) If S(z) is positive definite for a.e z.sup.n with respect to normalized Lebesgue measure =dx/(2).sup.n and satisfies the Paley-Wiener condition
.sub.T.sub.n log det Sd>,
then it admits the spectral factorization

(17) $\begin{array}{cc}S\left(z\right)=S^{+}\left(z\right)S^{-}\left(z\right),& \\ \mathrm{where}& \\ S^{+}\left(z\right)=\underset{kH}{\overset{}{.Math.}}{A}_k{z}^k\mathrm{and}{S}^{-}\left(z\right)=\underset{kH}{\overset{}{.Math.}}{A}_k^{*}{z}^{-k}.& \left(3\right)\end{array}$

(18) Here (3) has the following properties: 1. H is a so called non-symmetric half plane: H(H)=.sup.n and H(H)={0} containing {(k.sub.1, k.sub.2, . . . , k.sub.n).sup.n: k.sub.1>0}; 2. .sub.kHtr(A.sub.k,A.sub.k*)<; 3. S.sup.+ is outer: .sub.T.sub.n log|det S.sup.+|d=log|det A.sub.0|; 4. A.sub.0 is positive definite.

(19) S.sup.+ with properties 1-4 is unique, and we will always assume that these conditions are satisfied.

(20) In one embodiment, a method provides an approximate computation of coefficients A.sub.k in (3) for given coefficients C.sub.k in (2). The embodiment consists of the following procedures:

(21) Procedure 1 (Triangular Factorization).

(22) Performing the lower-upper triangular factorization of (1),

(23) $\begin{array}{cc}S\left(z\right)=M\left(z\right){\left(M\left(z\right)\right)}^{*},& \\ \mathrm{where}& \\ M\left(z\right)=\left(\begin{array}{ccccc}{f}_1^{+}\left(z\right)& 0& \mathrm{.Math.}& 0& 0\\ {}_{21}\left(z\right)& f_2^{+}\left(z\right)& \mathrm{.Math.}& 0& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ {}_{r-1,1}\left(z\right)& {}_{r-1,2}\left(z\right)& \mathrm{.Math.}& f_{r-1}^{+}\left(z\right)& 0\\ {}_{r1}\left(z\right)& {}_{r2}\left(z\right)& \mathrm{.Math.}& {}_{r,r-1}\left(z\right)& f_r^{+}\left(z\right)\end{array}\right).& \left(4\right)\end{array}$

(24) In (4), .sub.i.sup.+, i=1, 2, . . . r, are scalar spectral factors of det S.sub.i/det S.sub.i1, where S.sub.0=1 and S.sub.i is the left upper ii principle minor of S, and .sub.ijL.sub.1 (.sup.n), 2ir, 1j<i.

(25) Procedure 2 (Recurrent Construction).

(26) From m=2 until m=r step by step performing:

(27) Step 1 (Preparing an Auxiliary Matrix).

(28) Take the mm matrix-function

(29) $\begin{array}{cc}{F}_m\left(z\right)=\left(\begin{array}{cccccc}1& 0& 0& \mathrm{.Math.}& 0& 0\\ 0& 1& 0& \mathrm{.Math.}& 0& 0\\ 0& 0& 1& \mathrm{.Math.}& 0& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ 0& 0& 0& \mathrm{.Math.}& 1& 0\\ {}_1\left(z\right)& {}_2\left(z\right)& {}_3\left(z\right)& \mathrm{.Math.}& {}_{m-1}\left(z\right)& f_m^{+}\left(z\right)\end{array}\right),& \left(5\right)\end{array}$
where .sub.1(z), .sub.2(z), . . . , .sub.m(z), .sub.m.sup.+(z) are the first m entries of the mth row of the matrix M.sub.m1(z). It is assumed that M.sub.1(z)=M(z) (see (4)) and M.sub.m(z) is obtained during the mth iteration, m=2, 3, . . . , r.

(30) Step 2 (Expanding the Coefficients).

(31) Introduce the field =.sub.n1 of rational functions of n1 complex variables:
=.sub.n={P/Q: P,Q[z.sub.2,z.sub.3, . . . ,z.sub.n]}.

(32) Step 3 (Cutting the Tails).

(33) Represent the functions .sub.m.sup.+ and .sub.i, i=1, 2, . . . , m1, in (5) as polynomials in variable t:=z.sub.1 with coefficients from L.sub.2(.sup.n1):

(34) $\begin{array}{cc}f\left(t,z_2,\mathrm{.Math.},z_n\right)=\underset{j=0}{\overset{}{.Math.}}{d}_j\left(z_2,z_3,\mathrm{.Math.},z_n\right)t^j\mathrm{and}& \left(6\right)\\ {}_i\left(t,z_2,\mathrm{.Math.},z_n\right)=\underset{j=-}{\overset{}{.Math.}}{}_{ij}\left(z_2,z_3,\mathrm{.Math.},z_n\right)t^j& \end{array}$
and approximate functions in (6) by (Laurent) polynomials with coefficients from :

(35) $\begin{array}{cc}{f}_m^{+}{\hat{f}}_m^{+}=\underset{k=0}{\overset{N}{.Math.}}{\hat{d}}_k{t}^k\mathrm{and}{}_i{\hat{}}_i=\underset{k=-N}{\overset{N}{.Math.}}{\hat{}}_{\mathrm{ik}}{t}^{-k},{\hat{d}}_k,{\hat{}}_{\mathrm{ik}}\mathrm{��},& \left(7\right)\end{array}$
for some large integer N. Let {circumflex over (F)}.sub.m be the matrix (5) with .sub.m.sup.+ and .sub.i replaced by {circumflex over ()}.sub.m.sup.+ and {circumflex over ()}.sub.i, respectively.

(36) Step 4 (Construction of Multivariable Wavelet Matrix).

(37) Find a unitary matrix-function U.sub.m of the form

(38) $\begin{array}{cc}{U}_m=\left(\begin{array}{cccc}{u}_{11}& u_{12}& \mathrm{.Math.}& u_{1m}\\ u_{21}& u_{22}& \mathrm{.Math.}& u_{2m}\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ u_{m-1,1}& u_{m-1,2}& \mathrm{.Math.}& u_{m-1,m}\\ & & \mathrm{.Math.}& \end{array}\right),& \left(8\right)\\ \mathrm{where}& \\ u_{\mathrm{ij}}=\underset{k=0}{\overset{N}{.Math.}}{a}_k^{\left(\mathrm{ij}\right)}{t}^k,a_k^{\left(\mathrm{ij}\right)}\mathrm{��},=\underset{k=0}{\overset{N}{.Math.}}\stackrel{\_}{a_k^{\left(\mathrm{ij}\right)}}{t}^{-k}& \left(9\right)\end{array}$
such that det U.sub.m=1, and {circumflex over (F)}.sub.m.Math.U.sub.m is a matrix polynomial in variable t.

(39) The entries of (8) can be determined by considering the following system of equations (over the field ) in block matrix form

(40) $\begin{array}{cc}{\mathrm{��}}_j:=\{\begin{array}{c}{}_1.Math.X_m-D.Math.\stackrel{\_}{X_1}=0,\\ {}_2.Math.X_m-D.Math.\stackrel{\_}{X_2}=0,\\ \mathrm{.Math.}\\ {}_j.Math.X_m-D.Math.\stackrel{\_}{X_j}=1.\\ \mathrm{.Math.}\\ {}_{m-1}.Math.X_m-D.Math.\stackrel{\_}{X_{m-1}}=0.\\ {}_1.Math.X_1+{}_2.Math.X_2+\mathrm{.Math.}+{}_{m-1}.Math.X_{m-1}+D.Math.\stackrel{\_}{X_m}=0.\end{array}& \left(10\right)\end{array}$
where (see (7))

(41) 0$D=\left(\begin{array}{cccccc}{\hat{d}}_0& {\hat{d}}_1& {\hat{d}}_2& \mathrm{.Math.}& {\hat{d}}_{N-1}& {\hat{d}}_N\\ \mathrm{��}& {\hat{d}}_0& {\hat{d}}_1& \mathrm{.Math.}& {\hat{d}}_{N-2}& {\hat{d}}_{N-1}\\ \mathrm{��}& \mathrm{��}& {\hat{d}}_0& \mathrm{.Math.}& {\hat{d}}_{N-3}& {\hat{d}}_{N-2}\\ .& .& .& \mathrm{.Math.}& .& .\\ \mathrm{��}& \mathrm{��}& \mathrm{��}& \mathrm{.Math.}& \mathrm{��}& {\hat{d}}_0\end{array}\right),{}_i=\left(\begin{array}{cccccc}{\hat{}}_{i0}& {\hat{}}_{i1}& {\hat{}}_{i2}& \mathrm{.Math.}& {\hat{}}_{i,N-1}& {\hat{}}_{\mathrm{iN}}\\ {\hat{}}_{i1}& {\hat{}}_{i2}& {\hat{}}_{i3}& \mathrm{.Math.}& {\hat{}}_{\mathrm{iN}}& \mathrm{��}\\ {\hat{}}_{i2}& {\hat{}}_{i3}& {\hat{}}_{i4}& \mathrm{.Math.}& \mathrm{��}& \mathrm{��}\\ .& .& .& \mathrm{.Math.}& .& .\\ {\hat{}}_{\mathrm{iN}}& \mathrm{��}& \mathrm{��}& \mathrm{.Math.}& \mathrm{��}& \mathrm{��}\end{array}\right),0={\left(\mathrm{��},\mathrm{��},\mathrm{.Math.},\mathrm{��}\right)}^T{\mathrm{��}}^{N+1},\mathrm{and}1={\left(\mathrm{��},\mathrm{��},\mathrm{��},\mathrm{.Math.},\mathrm{��}\right)}^T{\mathrm{��}}^{N+1},$
and the column vectors
X.sub.i=(a.sub.i0,a.sub.i1, . . . ,a.sub.iN).sup.T.sup.N+1,i=1,2, . . . ,m,
are unknowns. Determining X.sub.i, i=1, 2, . . . , m1, from the first m1 equations of (10),
X.sub.i=D.sup.1.sub.iX.sub.m.sub.ijD.sup.11,i=1,2, . . . ,m1.(11)
and then substituting them in the last equation of (10), the latter reduces to
(.sub.1.sub.1*+.sub.2.sub.2*+ . . . +.sub.m1.sub.m1*+I.sub.N+1)X.sub.m=.sub.jD.sup.11.(12)
where .sub.i=D.sup.1.sub.i, i=1, 2, . . . , m1. For each j=1, 2, . . . m, (12) is a linear algebraic system of N+1 equations with (N+1) unknowns (in the field ). Its coefficient matrix is always non-singular. Thus (12) has a unique solution. Finding X.sub.m from (12) and then determining X.sub.1, X.sub.2, . . . X.sub.m1 from (11), we obtain the unique solution (X.sub.1.sup.j, X.sub.2.sup.j, . . . , X.sub.m1.sup.j, X.sub.m.sup.j) of the system , where
X.sub.i.sup.j:=(a.sub.i0.sup.j,a.sub.i1.sup.j, . . . ,a.sub.iN.sup.j).sup.T,i=1,2, . . . ,m.(13)

(42) If we construct a matrix

(43) $V=\left(\begin{array}{ccccc}{v}_{11}& v_{12}& \mathrm{.Math.}& v_{1,m-1}& v_{1m}\\ v_{21}& v_{22}& \mathrm{.Math.}& v_{2,m-1}& v_{2m}\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}\\ v_{m-1,1}& v_{m-1,2}& \mathrm{.Math.}& v_{m-1,m-1}& v_{m-1,m}\\ & & \mathrm{.Math.}& & \end{array}\right),$
by letting (see (13))

(44) $v_{\mathrm{ij}}=\underset{n=0}{\overset{N}{.Math.}}{a}_{in}^j{t}^n,1i,jm,\mathrm{then}$$U={V\left(V\left(1\right)\right)}^{-1}.$

(45) Step 5 (Iterative Step).

(46) Let

(47) $M_m=M_{m-1}.Math.\left(\begin{array}{cc}{U}_m& 0\\ 0& I_{r-m}\end{array}\right),$
where U.sub.m is determined in Step 4 by (8), and I.sub.rm is the identity matrix of order rm.

(48) As it was mentioned above, M.sub.m is used at the next iteration of the recurrent Procedure 2 at Step 1 when the number m increases by 1. Whenever m=r, it is assumed that
M.sub.r=M.sub.r1.Math.U.sub.r.(14)

(49) The matrix-function (14) is an approximate spectral factor of (1). As N.fwdarw. in (7), the difference between the computed and the exact spectral factors goes to zero in L.sub.2 norm.

(50) Procedure 3 (the Canonical Spectral Factor).

(51) In order to satisfy the uniqueness condition, we have to multiply a spectral factor on the right by a constant unitary matrix U which makes the product positive definite at the origin. Thus
S.sup.+=M.sub.r.Math.U.

(52) The method can be used for any dimensional multivariate matrix function for which the spectral factorization exists, including non-rational matrices. The method can be used for efficient implementation of engineering solutions to problems in n-Dimensional Filtering, Image and Video Compression, and Radar Systems, which are computationally reducible to multivariable matrix spectral factorization.

(53) Application to Granger Causality Test

(54) In one particular implementation, n-D MSF is utilized with the Granger causality test. Granger causality has emerged in the past years as a leading technique for inferring directions of neural interactions and information flow in the brain from corresponding electroencephalographic (EEG) and functional magnetic resonance imaging (fMRI) recordings. As it is shown in the paper of Dhamala et al Analyzing information flow in brain networks with nonparametric Granger causality, NeuroImage, vol. 41, no. 2, pp. 354-362, 2008, non-parametric methods of estimation of Granger causality (GC) is reduced to MSF and the same author demonstrated that GC can be used to identify exactly epilepsy seizure onset location in brain before the surgery (see Dhamala et al Localizing epileptic seizure onsets with Granger causality PHYSICAL REVIEW E 88, 030701(R), 2013).

(55) So far Wilson's algorithm of 1-D MSF is used by neuroscientists. However, in real-life problem applications, where power spectral density matrix (which have to be factorized) is usually noisy and frequently singular (which arise in biological systems with unstable modes; see Friston et al Granger causality revisited DOI: 10.1016/j.neuroimage.2014.06.062) above mentioned 1-D MSF algorithm outperforms Wilson's algorithm in accuracy (a publication on this topic is in progress).

(56) As Granger causality is based on Wiener's theory of prediction of stationary stochastic processes, which can be generalized to multi-parameter stationary processes as well, a theory of multivariable Granger causality can be created and tested for the analysis of EEG and fMRI data as these recordings are 2-dimensional or even 3-dimensional by its nature. Since n-D MSF will be required for multivariable Granger causality, this perspective opens new opportunities for practical applications of novel n-D MSF method. These fields include research on neurological and psychological diseases such as Epilepsy, Schizophrenia, Sleep-wake regulatory system, Parkinson, Refractive Chronic pain, Multiple Sclerosis, Lateral Sclerosis, Alzheimer.

(57) Application to n-D Wiener Filtering

(58) A signal that is transmitted from a sender to a receiver is often impaired by various forms of distortions. Wiener filtering is a method to recover the original signal as accurately as possible from the received signal. The necessity of this frequently arises in signal detection, prediction, estimation, stochastic control, missile guidance, aircraft stabilization, economic forecasting, seismic data processing, etc.

(59) If the multidimensional signal s.sub.i depends on a single parameter i, e.g. for stochastic vector time series, then Wiener filtering requires 1-D MSF. However, in applications where S.sub.i.sub.1.sub.i.sub.2.sub.. . . i.sub.n depends on several parameters, e.g. for video images, radar screens (n=2) or tomographic signal analysis (n=3), Wiener filtering is reduced to multivariate system of Wiener-Hopf equations which requires n-D MSF.

(60) Application to Wavelet Compression

(61) Wavelet compression is a form of data compression using the so-called wavelet transform. It is often employed for compression or coding of structured information, e.g. for compression of image, video or audio signals. The goal is to store the data in as little space as possible. Performing the wavelet transform and removing the coefficients that are outside a theoretical threshold shrinks the existing data performing a lossy compression. Such information is more suitable for storage and transmission. When the inverse wavelet transform is performed, information can be reconstructed without producing significant distortion, if the removed coefficients for this compression are appropriately selected. If the considered data depends on several parameters, then multivariable wavelets are involved in the process instead of usual wavelets.

(62) A challenge in every specific practical problem of wavelet compression is to select how to remove the superfluous coefficients. One important factor in this system is the way one decides which information is less important and should be discarded. The short list of known multivariable wavelets restricts the area of applications of the compression method described above.

(63) An exemplary implementation of the present invention may provide a complete classification of a new rich class of multivariable wavelets. The computational procedures for construction of such wavelets is described in Step 4 of Procedure 2. Having quick access to the complete bank of such multivariable wavelets, opens the possibility of choosing the best possible selection, thereby maximizing the compression level for a given level of accuracy in signal reconstruction.

(64) As shown in FIG. 1, e.g., a computer-accessible medium 120 (e.g., as described herein, a storage device such as a hard disk, floppy disk, memory stick, CD-ROM, RAM, ROM, etc., or a collection thereof) can be provided (e.g., in communication with the processing arrangement 110). The computer-accessible medium 120 may be a non-transitory computer-accessible medium. The computer-accessible medium 120 can contain executable instructions 130 thereon. In addition or alternatively, a storage arrangement 140 can be provided separately from the computer-accessible medium 120, which can provide the instructions to the processing arrangement 110 so as to configure the processing arrangement to execute certain exemplary procedures, processes and methods, as described herein, for example. The instructions may include a plurality of sets of instructions. For example, in some implementations, the instructions may include instructions for applying radio frequency energy in a plurality of sequence blocks to a volume, where each of the sequence blocks includes at least a first stage. The instructions may further include instructions for repeating the first stage successively until magnetization at a beginning of each of the sequence blocks is stable, instructions for concatenating a plurality of imaging segments, which correspond to the plurality of sequence blocks, into a single continuous imaging segment, and instructions for encoding at least one relaxation parameter into the single continuous imaging segment.

(65) System 100 may also include a display or output device, an input device such as a key-board, mouse, touch screen or other input device, and may be connected to additional systems via a logical network. Many of the embodiments described herein may be practiced in a networked environment using logical connections to one or more remote computers having processors. Logical connections may include a local area network (LAN) and a wide area network (WAN) that are presented here by way of example and not limitation. Such networking environments are commonplace in office-wide or enterprise-wide computer networks, intranets and the Internet and may use a wide variety of different communication protocols. Those skilled in the art can appreciate that such network computing environments can typically encompass many types of computer system configurations, including personal computers, hand-held devices, multi-processor systems, microprocessor-based or programmable consumer electronics, network PCs, minicomputers, mainframe computers, and the like. Embodiments of the invention may also be practiced in distributed computing environments where tasks are performed by local and remote processing devices that are linked (either by hardwired links, wireless links, or by a combination of hardwired or wireless links) through a communications network. In a distributed computing environment, program modules may be located in both local and remote memory storage devices.

Example Implementations

(66) An exemplary implementation of the present invention may be an apparatus, such as a computer device, illustrated in FIG. 2. The apparatus may include a receiver 210 configured to receive a signal input 220 whose characteristics may be described by means of a high-dimensional matrix with multivariable high-order polynomial or non-rational entries. This can be expressed, for example, as being that the receiver 210 is configured to receive a signal input describable with a high-dimensional matrix with high-order polynomial or non-rational entries. When it is said that the signal is so describable, it should be understood that it is intended that the signal cannot be characterized more simply. One of ordinary skill in the art will appreciate that the characterization of signals as they occur in wireless communications may be characterized according to this description. Other signals are, of course, not excluded.

(67) The apparatus may also include a processor 230 configured for estimating a message from the received signal using a filtering technique. A person of ordinary skill in the art would appreciate that many filtering techniques may be applicable to the problem at hand, namely estimating a message from a received signal. The filtering, may in some implementations employ the method of n-D Matrix Factorization described earlier. The processor 230 may be the same physical device as the receiver 210, or the receiver 210 and the processor 230 may be separate physical devices. For example, in some implementations, the processor 230 may be a general purpose processor and the receiver 210 is an input port for the processor. In another example, both the processor 230 and receiver 210 are the same application specific integrated circuit. These examples are not meant to be limiting. The processor 230 may be specifically configured to perform matrix calculations and may be provided with suitable logic circuitry and software programming to accomplish matrix mathematics and manipulations described throughout this patent application.

(68) The apparatus can further include a transmitter 240 configured to provide a real-time output 250 of the filtering. The transmitter 240, like the receiver 210, can be implemented either as a discrete physical element or as an integrated component with either or both of the receiver 210 and the processor 230.

(69) Although the above apparatus has been characterized in terms of performing filtering implementations, one of ordinary skill in the art would appreciate that suitable modifications to the above apparatus could be made to configure the processor 230 to perform data compression such as wavelet compression.

(70) The signal input 220 may, in some implementations, be a noisy signal of a wireless communication system (not shown). The output signal from the output 250 can be a repaired version of the received signal from which noise has been removed. In some implementations, output 250 is a real-time output.

(71) FIG. 3 illustrates a method according to an example implementation. The method may include receiving 310 a complex signal input depending on several parameters whose characteristics may be described by means of a high-dimensional matrix with multivariable high-order polynomial or non-rational entries. The filtering may employ 320 multivariable matrix spectral factorization. The method may further include providing 330 a filter output depending on several parameters.

(72) The signal input can be, for example, a noisy signal of a wireless communication system. The output signal can be, for example, a repaired version of the received signal from which noise has been removed. Thus, the method can provide a concrete and tangible output signal. The method can be implemented in such a way that each step of the method is performed by a computing device. Thus, one implementation of the present invention is a non-transitory computer-readable medium (such as a recording or storage medium) encoded with instructions that, when executed on a computing device perform the method.

(73) Another exemplary implementation of the present invention is a method for estimating a message from a received signal at a receiver. For example, multiple mobile units 401 (i.e. 401 a, 401 b . . . 401 r) could send messages to a base station as seen in FIG. 4. The messages from the received signals need to be estimated simultaneously.

(74) FIG. 5 is an example implementation that provides for a logic unit such as a processor that takes a noisy signal as an input and provides for an estimate of the message included in the noisy signal. The processor may employ filtering along with the method of multivariable matrix spectral factorization described earlier. The processor may apply other filtering techniques that are computationally reducible to a state where the method of multivariable matrix spectral factorization yields spectral factors, which are used in construction of the filter.

(75) FIG. 6 is another example implementation of the present invention. This implementation provides for a method of determining coefficients for a filter that will allow for estimating a message from a noisy input signal. In this method, 601 a pre-computed measure of the channel characteristics (which is in the form of a multivariable spectral density matrix function), is factorized 602 into two spectral factors. In 603 the filter coefficients (which describe the impulse response of the filter) are determined from the spectral factors determined in 602. The precomputed measurements such as the spectral characteristics of the signal are assumed known. In practice they are computed ahead of time based on signal characteristics and channel qualities or by monitoring the source (at the source). For example, the source in may be monitored, the characteristics then computed, and then separately communicated to the receiver in order to calibrate the filter correctly. Nonetheless there may be cases where the signal characteristics are not precomputable and have to be estimated on-line.

(76) FIG. 7 describes the processor 501 in FIG. 5 in greater detail. It must be noted that the two processors in FIG. 7 may be the same integrated circuit or logic component or may be different integrated circuits or logic components. Specifically, processor 1 may compute the filter coefficients based on the precomputed spectral characteristics of the channel and/or the incoming signal. The processor 1 may include logic components for receiving the precomputed spectral characteristics, which may be described by a means of a high-dimensional matrix with multivariable high-order polynomial or non-rational entries. Processor 1 may also include logic components for computing canonical spectral factors of the received characteristics. Processor 1 may further include logic components for computing filter coefficients using the computed canonical spectral factors. In FIG. 7, the processor 2 may be further decomposed into additional logic components, which perform functions such as taking N samples of the incoming signal y.sub.i. These samples would then be output to another logic block within processor 2 that would compute the estimated signal or message based on coefficients of the filter computed by processor 1 and the original input signal y.sub.i.

(77) Various embodiments are described in the general context of method steps, which may be implemented in one embodiment by a program product including computer-executable instructions, such as program code, executed by computers in networked environments. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. Computer-executable instructions, associated data structures, and program modules represent examples of program code for executing steps of the methods disclosed herein. The particular sequence of such executable instructions or associated data structures represents examples of corresponding acts for implementing the functions described in such steps.

(78) Software and web implementations of the present invention could be accomplished with standard programming techniques with rule based logic and other logic to accomplish the various database searching steps, correlation steps, comparison steps and decision steps. It should also be noted that the words component and module, as used herein and in the claims, are intended to encompass implementations using one or more lines of software code, and/or hardware implementations, and/or equipment for receiving manual inputs.

(79) As used herein, the singular forms a, an and the include plural referents unless the context clearly dictates otherwise. Thus, for example, the term a member is intended to mean a single member or a combination of members, a material is intended to mean one or more materials, or a combination thereof.

(80) As used herein, the terms about and approximately generally mean plus or minus 10% of the stated value. For example, about 0.5 would include 0.45 and 0.55, about 10 would include 9 to 11, about 1000 would include 900 to 1100.

(81) It should be noted that the term exemplary as used herein to describe various embodiments is intended to indicate that such embodiments are possible examples, representations, and/or illustrations of possible embodiments (and such term is not intended to connote that such embodiments are necessarily extraordinary or superlative examples).

(82) The terms coupled, connected, and the like as used herein mean the joining of two members directly or indirectly to one another. Such joining may be stationary (e.g., permanent) or moveable (e.g., removable or releasable). Such joining may be achieved with the two members or the two members and any additional intermediate members being integrally formed as a single unitary body with one another or with the two members or the two members and any additional intermediate members being attached to one another.

(83) It is important to note that the construction and arrangement of the various exemplary embodiments are illustrative only. Although only a few embodiments have been described in detail in this disclosure, those skilled in the art who review this disclosure will readily appreciate that many modifications are possible (e.g., variations in sizes, dimensions, structures, shapes and proportions of the various elements, values of parameters, mounting arrangements, use of materials, colors, orientations, etc.) without materially departing from the novel teachings and advantages of the subject matter described herein. Other substitutions, modifications, changes and omissions may also be made in the design, operating conditions and arrangement of the various exemplary embodiments without departing from the scope of the present invention.

(84) While this specification contains many specific implementation details, these should not be construed as limitations on the scope of any inventions or of what may be claimed, but rather as descriptions of features specific to particular implementations of particular inventions. Certain features described in this specification in the context of separate implementations can also be implemented in combination in a single implementation. Conversely, various features described in the context of a single implementation can also be implemented in multiple implementations separately or in any suitable subcombination. Moreover, although features may be described above as acting in certain combinations and even initially claimed as such, one or more features from a claimed combination can in some cases be excised from the combination, and the claimed combination may be directed to a subcombination or variation of a subcombination.