Modeling and investigating the stability of a solution to the inverse problem of signal separation

Abstract

This paper proposes a method for modeling and analyzing the stability of a solution to the inverse problem of extracting individual signals from an additive mixture of several signals that come to measurement points from various signal sources inaccessible for direct measurement. Stability analysis is accomplished by determining those intervals (singular intervals) for parameters of a signal formation model in which steady signal separation is achievable. We have developed algorithms to calculate singular intervals for different parameter variations of a signal formation model-absolute, relative, critical, and their combinations-that simulate various practically significant types of model parameter perturbations that affect the stability of the solution to this inverse problem. The paper also presents the results of computer modeling for the proposed algorithms.

Keywords

• signal separation
• inverse problem
• solution stability
• signal models
• singular intervals
• algorithm
• modeling

1. Introduction

H

2 exhibit limited functionality.

Indeed, values cond H  and H 2

are integral estimates of stability, and they do not allow singular intervals H to be determined in singular-interval matrices H , which is important for practical applications. It is evident that the knowledge, in matrices, of elements (singular intervals) close to zero makes it possible to determine elements of mixing matrices H on which the stability of the problem of signal separation mainly depends. In other words, values cond H  and H do not take into 2 account the structure of a perturbation (for the same condition numbers and matrix norms, there can be an infinite number of perturbation realizations). But in practice, perturbations can have a structure: Each matrix element can have its own perturbation that is unlike the others, and that perturbation can, in turn, be absolute, relative, or critical—or a combination of the three.

Reference [6] proposes a method for analyzing the stability of the solution to a system of linear algebraic equations, offering

Mathematical Modeling / V.А. Zasov, Ye.N. Nikonorov broader functionality compared with the methods described above. The method can be used for analyzing and verifying the stability of the solution to the problem of signal separation. The algorithm that uses that method determines the direction of the worst parameter variations that cause instability (singularity). If, in a set parameter interval, the condition number for absolute or relative variations has increased significantly (e.g., exceeded a threshold), a solution within this interval is assumed unstable. Thus, the algorithm makes it possible to analyze the stability of a solution for signal formation models at a set variation value of mixing-matrix elements.

The method proposed in [10] does not solve the problem of determining the matrix H of singular parameter intervals; nor does it enable use of complex mixing matrices Η   , and that limits the method’s functionality.

Thus, our analysis of existing methods’ functionality indicates the relevance of developing a method for modeling, analyzing, and verifying the stability of the solution to the problem of signal separation.

This paper proposes analyzing stability by determining singular intervals with the model’s parameter variations directed toward the maximal deterioration of the solution’s stability.

2. The object of the study

To state the problem formally, we will consider a signal formation model presented as a linear multivariable system that has N inputs and M outputs. The model’s input signals are sn  k  , n  1, 2,..., N ; output signals, xm k  , m  1, 2,..., M . The input signals are generated by various signal sources, and the output signals may be signals of various receivers such as sensors, measurement transducers, and antennas. Let us assume that each of the M outputs of the multivariable system is connected with all the N inputs through linear signal transmission channels.

At any discrete instant of time k, the M -dimensional vector of sensor-measured discrete signals

T T x  k    x1 k  , x2 k  ,..., xM k  results from the N -dimensional vector of source signals s k   s1  k  , s2  k  ,..., sN k  . The mathematical model of signal formation is described by an equation system of discrete convolution type ( 1 ), where the m th observed signal is an additive mixture of channel-distorted source signals and noise [7]; that is,

N G1 xm k     hmn  g, l sm k  g   ym k  , ( 1 )

n1 g0 where hmn  g, l is the element M×N of the h  g, l matrix for the impulse characteristics of channels, and

T y  k    y1  k  , y2 k  ,..., yM  k  is the noise vector. For purposes of further discussion, we will assume that the hmn  g, l impulse characteristics are finite and are represented by the counting number G . The dynamic characteristics of channels hmn  g,l are quasistationary in that they change depending on parameter vector l (time, temperature, location, etc.).

In the frequency domain, model (1) is described as

X    H  , l   S    Y   ,  H11  , l   where H  , l   

H1N  , l  

 - is the mixing matrix M  N , comprising Fourier transforms of the channels; of separating source signals is the solution to system ( 1 ), and it can be expressed as

M G1 sn k     wnm  g, l  xm  k  g  ,

m1 g0 where w  g, l is the matrix of impulse characteristics of tunable filters with wnm  g, l  elements. In the frequency domain, equation ( 3 ) can be written as

S    W  , l X   , where W  , l   H-1  , l . It is evident that calculating the separating matrix w  g,l requires prior information about parameters of the signal formation model (object parameters). For separating signal sources, a variety of approaches are used that are based on various prior knowledge of the item under study. Signal separation methods can be classified into two groups—deterministic and statistical [1]. X     X1  , , X M   S    S1   , , SN   Y    Y1  , ,YM  

T T

is the vector of observed signals, and it comprises Fourier transforms of receiver signals; is the vector of source signals, and it comprises Fourier transforms of source signals; is the noise vector, comprising Fourier transforms of noise signals. Signals of sources S  and of noise Y   are considered independent, and channels can be modeled by spectral converters such as various filters.

Generally, the solution to the problem of separating signal sources reduces to calculating the separating matrix w  g  , which is, in terms of specific criteria, equal or close to the matrix inverse to matrix h  g, l  . Thus, generally, the solution to the problem  H M1  , l 

H MN  , l   ( 2 ) ( 3 ) ( 4 )

Mathematical Modeling / V.А. Zasov, Ye.N. Nikonorov

The deterministic group is based on prior information about characteristics of signal transmission channels—that is, on the knowledge of the matrix of impulse characteristics h  g, l , which are either measured or determined from theoretical premises.

A feature of the statistical group is that h  g, l matrix elements are unknown explicitly, and the information used to determine input signals s  k  is provided by the realization of the vector of measured signals x  k  and the knowledge of source properties of signals sk  .

The deterministic group is based on principal information about signal transmission channels (statistical, frequency, amplitude, and other channel characteristics); that is, transmission channels and signals are known.

The statistical group is based on principal information about signal sources such as lacking source correlation and the knowledge of signal distribution laws. In this case, explicit information about transmission channels is unavailable, and only observed signals are known. For that reason, the methods within this group are often called “blind” [8].

Thus, the solution to the problem of separating of signal sources reduces to using a deterministic or statistical method to calculate the separating matrix w  g, l equal or close, in terms of specific criteria, to the matrix inverse to matrix h  g, l .

There are separation methods that fall within neither group because they use information both about channels and the properties of signal sources (e.g., adaptive noise concellation [9]).

From general solution ( 3 ) it follows that the problem of signal separation relates to the class of inverse problems, which may be ill-posed in the general case.

Our paper aims to: —Develop an algorithm for modeling the problem of signal separation with a solution whose stability is variable by setting variations for the parameters of the signal formation model.

—Develop algorithms for analyzing and veryfying stability by determining parameter intervals in which stable signal separation is achievable for various practically significant variations of model parameters.

This paper investigates the stability of the solution to the problem of signal separation with varied parameters of channels

Hmn  ,l  , constituting the mixing matrix H  ,l  .

3. Methods. Algorithms for Modeling, Analyzing, and Verifying the Stability of the Solution to the Problem of Signal

Separation

3.1. Mathematical Signal Formation Model with the Capability to Set Variations for Channel Parameters

To investigate how prior indefinite perturbations affect stability, we propose introducing singular-variation blocks for parameters of channels  hmn into the signal formation model. Then the signal formation model with parameter variations shown in figure 1 will take the form of [7]

N G1 xm  k      hmn  g, l   hmn  g, l  sm  k  g   ym  k  ( 5 ) n1 g 0 In the frequency domain, expression ( 5 ) can be written as

Unlike objectively existing perturbations, parameter variations in the model for stability studies can be modeled by introducing a block for setting types of variation. Thus, mathematical model ( 5 ) can be used to investigate how perturbations from various types of variation affect the stability of the solution to the problem of signal separation.

For purposes of further discussion, we will refer to matrices of parameter intervals varying from the initial state H  ,l  to the degenerated (singular) state H  , l  as singular-interval matrices and designate them H,l .

Among the different types of variations, we will consider those most often encountered in engineering practice—absolute, relative, and critical variations, which simulate related real perturbations [7]. Critical variations are variations that cause the initial model ( 5, 6 ) to become degenerated at a minimal spectral variation norm of  H  ,l  . Relative variations, as the name 2 suggests, have values proportional to those of matrix elements. Absolute variations can be of any value unconnected with the value of the current matrix element. Thus, this paper aims to determine singular intervals for parameters Habs  , l  , habs  g, l , Hrel  , l  , hrel  g, l , Hcrit  , l  , and hcrit  g , l  for the variations above. In the introduced matrices of singular parameter intervals, mn th elements Hmn indicate changes in parameters of mn th elements of the initial matrix H  , l  .

In particular, if model channels are frequency-independent and parameter vector l independent, the designations of singularinterval matrices omit arguments   ,  g  and l  ; for instance, Habs , habs .

Thus, the singular intervals obtained from calculations reflect those absolute, relative, and critical perturbations of the signal formation model’s parameters that cause the model to be unstable.

X     H  , l    H  ,l   S    Y   , where  H  ,l  is the matrix of singular parameter variations. ( 6 ) 3.2. Analyzing and Verifying the Stability of Signal Separation by Determining Singular Parameter Intervals for the Signal Formation Model

For purposes of determining singular parameter intervals for different variations, a generalized algorithm has been developed [7, 10], in which three stages can be distinguished: determining the singular direction of parameter variation; determining a singular matrix; and determining a singular-interval matrix.

Singular directions for absolute, relative, and critical variations are determined by direction matrices whose analytic expressions, obtained in references [7, 10], are given in table 1.

Direction matrices can be calculated both on the basis of singular value decomposition (SVD) and on the basis of the inverse matrix. Determining singular directions with proposed matrices Z has lower computational complexity compared with known algorithms. 2 2

The proposed matrices Z can be used to determine singular parameter intervals not only for real elements (as in known algorithms) but also for complex (frequency-dependent) elements of mixing matrix Η   . sign(A) , matrix operation whose elements are calculated as sign( Amn )  Amn / Amn ;  , element-by-element multiplication of matrices C  A  B , where Cmn  Amn  Bmn ; vn and un , right and left singular vectors of singular value decomposition H=UΣV*  nN1 nunvn ; 1 , the maximum column sum matrix norm.

It is proposed that singular matrix H be calculated by finding the roots of the equation f (H j   h  Z)  det(H j   h  Z)  0 under restrictions caused by parameter variations.

The numerical algorithm (table 2) for determining singular matrices H for absolute, relative, and critical variations is based on the Newton method, in which, unlike in the classical method, derivative fZ' j (H j ) is calculated on the basis of the matrix of directions Z and refined in each step. This improves accuracy and simplifies computation compared with known algorithms [10].

At the third stage, singular-interval matrix H is calculated as follows: H  H  H . In the proposed algorithm, function f (H j   h  Z) must satisfy the conditions of convergence theorems from the Newton method, including the Lipschitz condition. Based on inverse matrix Based on

SVD 

H1

2  uN vN  

A  sign(H)

1 A  sign(uN vN )

A  sign(uN vN ) If f  H j1   f  H j    , then algorithm ends ( H  H j ); else,

Parameter   0 is set, and it determines error, increment value  h , and initial iteration value j  1 Z j is determined according to type of parameter variation f (H j  h  Z j )  f (H j )

 h 2 3 4 5 6 1 2 3 4 5 6 7 stable ( H R ( g , l)  H( g , l)  Ht ( g , l) ) and unstable ( HS ( g , l)  H( g , l)  H П ( g , l) ) separation If Hmax ( g , l)  H R ( g , l) , solution is stable; otherwise message appears stating that stable signal separation for frequency of  g is impossible If H pot ( g , l)  H R ( g , l) , solution is stable; otherwise message appears stating that stable signal separation for frequency of  g is not guaranteed g  g  1 . If g  G 1 , algorithm ends, and final message on stability verification appears; else, step 2

Initialization For frequency  g For frequency  g For frequency  g Conditions of separation stability at frequency of  g are verified Conditions of stable separation at frequency of  g are verified Transition to next spectral matrix

The matrix H max ( g , l) added in step 5 for maximal allowable variation intervals is defined from theoretical and practical information about the object being modeled. Matrix inequalities of

A  B type should be understood as systems of

componentwise inequalities Amn  Bmn .

Threshold matrix H t  g , l  , determined in step 3 of the algorithm, is mixing matrix H j  g , l  , for which condH j  g , l  exceeds a given threshold value of condt . To determine matrix H t  g , l  , mixing matrix H j  g , l  is changed in accordance with the expression H j  g , l  =H  g , l  +j  H  g , l  , and in each step j  1,, J its condH j  g , l  is compared with threshold value condt .

The calculated matrix Ht  g , l  of threshold values serves as the basis for determining the matrix of parameter intervals for stable separation H R  g , l   H  g , l   Ht  g , l  and the matrix of parameter intervals for unstable separation H S  g , l   H  g , l   Ht  g , l  .

4. Results and Discussion

H Figure 2 shows the relationship between relative error 

in determining singular intervals H and the reduced error of the parameters of mixing matrix H (determined by the number of binary digits of the ADC) and its values cond H  for critical parameter variations. Figure 3 shows results testing algorithms for verifying the stability separation of signals. number of bits of the ADC) under critical parameter variations.

The proposed algorithms have been incorporated in a software system for modeling signal separation and restoration. Figure 4 shows examples of modeling and investigating the stability of signal separation for test signals and signals in an automatic cab signaling system, which transmits, via the track, traffic-light coding signals to train cab [11].

The automatic cab signaling system, which is used for train safety, operates under the influence of various interference sources. Suppressing that interference is important for the reliable operation of the system. Sometimes for interference sources to be suppressed, interference signals need to be extracted in order to determine their physical nature; that is, to identify interference sources [11]. This needs to be done as part of monitoring the condition of track circuits and automatic cab signaling systems.

Figures 4-а( 1 ) and 4-а( 2 ) show initial triangular test signals and their mixtures, and figures 4-а( 3 ) и 4-а( 4 ) are examples of a unstable and an stable solution to the problem of separating test signals. The Information window indicates that the separation is unstable: singular intervals at a frequency of 400 Hz are close to zero, and the condition number is on a sharp increase.

Figures 4-b( 1 ) and 4-b( 2 ) show examples of the automatic cab signaling system’s amplitude-modulated signals under the influence of interference: fluctuation noise from traction current, a 50 Hz harmonic interference from the power line, and a lowfrequency interference of 4 Hz due to intake coils’ wobbling in relation to the track. Figures 4-b( 3 ) and 4-b( 4 ) illustrate unstable and stable separation of signals in the system and the above interference. Whether the solution is stable or unstable is displayed in the Information window.

This results confirms the possibility of using the developed algorithms in engineering applications.

5. Conclusion

The key results of our investigation are as follows:

We proposed an algorithm for modeling signal separation that makes it possible to study the stability of solutions to the problem of signal separation under stability-crucial parameter variations (perturbations) controlled in a signal formation model.

We also developed algorithms for analyzing and verifying stability by determining singular intervals for parameters of the signal formation model for various parameter variations.

References

[1] Bakushinskiy AB , Goncharskiy AV . Ill-Posed Problems: Numerical Methods and Applications . Moscow: Moscow State University Press, 1989 ; 199 p. (in Russian)

[2] Petrov Yu .P, Sizikov VS . Well-Posed , Ill-Posed, and Intermediate Problems with Applications: A Textbook for Institutes of Higher Education . Saint Petersburg: “Politekhnika” Publisher, 2003 ; 261 p. (in Russian)

[3] Digital Signal and Image Processing in Radiophysical Applications. Ed. Kravchenko VF . Moscow: “Fizmatlit” Publisher, 2007 ; 544 p. (in Russian)

[4] Tyrtyshnikov YeYe. Matrix Analysis and Linear Algebra . Moscow: “Fizmatlit” Publisher, 2007 ; 480 p. (in Russian)

[5] Demmel J. Applied Numerical Linear Algebra . Theory and applications . Moscow: “Mir” Publisher , 2001 ; 430 p. (in Russian)

[6] Petrov Yu P. Obtaining Reliable Solutions to Equation Systems . Saint Petersburg: Izdatelstvo “BKhV-Peterburg” Publisher, 2009 ; 176 p. (in Russian)

[7] Zasov VA . Algorithms and Computational Devices for Separating and Restoring Signals in Multivariable Dynamic Systems: A Monograph . Samara: Samara State Transport University Press, 2013 ; 233 p. (in Russian)

[8] Cichocki A , Amari Sh . Adaptive Blind Signal and Image Processing: Learning algorithms and applications . John Wiley & Sons Ltd, 2002 ; 555 p.

[9] Windrow B , Stearns S . Adaptive Signal Processing. Moscow: “Radio i svyaz” Publisher , 1989 ; 440 p. (in Russian)

[10] Zasov VA , Nikonorov YeN . Algorithms for Verifying the Stability of a Solution to the Problem of Separating Signal Sources under Conditions of Prior Uncertainty . Published in Hardware and Software Means for Management, Control, and Measurement Systems: Proceedings of a Conference with Russian and International Attendance. Moscow: Russian Academy of Sciences, Trapeznikov Institute of Control Sciences Press , 2010 ; 482 - 491 . (in Russian)

[11] Zasov VA , Nikonorov YeN , Tarabardin MA. Identifying Input Signals in Problems of Controlling and Diagnosing Dynamic Objects . Proceedings of the IV International Conference on Control Problems . Moscow: Russian Academy of Sciences, Trapeznikov Institute of Control Sciences Press, 2009 ; 1478 - 1486 . (in Russian)