Localization of Point Sources with Random Spatial Position and Random Discipline of Pulse Generation

Abstract

The methods and speed-optimal algorithms oriented to spatial localization of pulsed-point sources manifesting themselves at random time by generation of instantaneous delta pulses are discussed. Optimal search procedures have been proposed that are focused on the localization of random pulsed-point objects in standard and advanced search modes (for example, in the absence of a priori information about the intensity of the source or when its density is unknown within the search interval).

Keywords

• optimal search
• random pulsed-point source
• localization accuracy
• receiver

Introduction

Introducing the binary function x

For the random priori distribution of a pulsed source on the x-axis, the construction of even a one-step (which ends immediately when the first pulse is registered) time-optimal search procedure causes considerable difficulties. In one-step periodic search algorithms, the relative load φ(x) on the point x (that is, the relative time it’s located in the view window) remains constant throughout the entire search time. With this approach, the problem is to find the function φ(x), minimizing the average search time when the following conditions are met   1   f (x)  (x)

dx  ( x)dx   , 0   ( x)  1. ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) ( 6 )

Optimization of expression ( 1 ) with constraints ( 2 ) - ( 3 ) belongs to non-linear programming problems [6-7]. To solve it, we will use the method of Lagrange multipliers [8] and we will look for the function φ(x) minimizing the expression Differentiating by φ and taking into account the constraint ( 2 ), we obtain  f ( x)    ( x)

   ( x)dx.

  (x)   f ( x)  f ( x)dx .

If for any x condition ( 3 ) is not violated, then function ( 4 ) is a solution to the formulated extremal problem. If there exist such domains x, where the solution φ(x)> 1, then inside these areas it is necessary to put φ(x) = 1, and to recalculate (for the remaining points) the indefinite factor µ taking into account the already changed conditions ( 2 ) and ( 3 ). After that, any binary function u(x, t) can be selected as the optimal search strategy if it satisfies the relations  u( x, t )dx   ;

 u( x, )d   ( x)t.

In the general case, building an optimal (not necessarily periodic) one-step search algorithm is associated with finding such a function φ(x, t) – the relative load on point x at time t, – which minimizes the average localization time provided that and for any t t    dt dxf ( x) exp(   ( x, )d )

0 0   ( x, t)  1  ( x, t)dx   .

t To simplify further calculations, we introduce a function  ( x, t )   ( x, )d corresponding to the total take into account constraints ( 5 ) and ( 6 ), we again introduce the Lagrange multiplier μ(t). Then the task of building an optimal search strategy will be reduced to finding the function α(x,t) minimizing the functional  dt  dxexp(  (x, t) f (x)   (t) (x, t), provided that

The solution to this variational problem is the function   (x, t)dx  t,  0   ( x, t)  t.

 1 0, ln    1  (x, t)   ln  t, t  1 ln   f (x)  (t) f (x)  (t) f (x)  (t)

, ( 8 ) ( 9 ) where the multiplier μ(t) is determined from relation ( 7 ), and any binary function can be chosen as the optimal search strategy u(x, t) that satisfies the conditions t  u( x, )d   ( x, t ); 0  u( x, t )dx   .

The use of optimal search algorithms in practice leads to certain difficulties. The fact is that in those cases when source’s priori distribution density function differs from the uniform one, both of the proposed optimal one-step search algorithms cannot be physically realized by moving the singly connected (non-separable) scanning window. Therefore, in actual search procedures, it is advisable to perform a one-step procedure according to the following scheme. The interval (0, L) is pre-divided into a series of discrete elements having a length ε, and the a priori given density f(x) is “stepwise” approximated on each of them. The value of ε is considered to be sufficiently small (which meets the high requirements for localization accuracy) so that the variation of the function f(x) within one discrete can be neglected. The search must begin with “observation” of the highest “peak”, within which the amplitude function f(x) is maximum, then after the time t1, the window is alternately set under the two highest “peaks”, then after the time t2, three elements are alternately observed, etc. All switching moments ti are determined in exact accordance with the above relation ( 8 ), which is the basis for constructing an optimal search strategy.

It should be noted that the search algorithm under discussion assumes that the intensity of the source λ is known in advance. If such a priori information is not available, it is possible to recommend a periodic procedure that does not depend on this intensity. In accordance with this strategy, the integrals of the density f(x) are initially calculated in each ε-discrete. If the total number of ε-increments (into which the initial search interval is divided) is m, and the “step” integrals over each of them are equal to P1,P2, ...,Pm, then the view window should cycle through all discretes with relative load  i 

Pi m  j1

P j , ( j 1,...,m).

These βi values are easy to obtain if the method of Lagrange multipliers is used again to minimize the average search time:   (1  )(P1 1  P2  2  ...  Pm  m )  min, ( 1  ...   m  1). 3

Multi-step search algorithms

With high requirements for localization accuracy, one-step algorithms are far from optimal. So, when constructing an optimal search procedure, we cannot limit ourselves to one-step algorithms, and should consider a search procedure consisting of several steps. For the average time of the m-step localization procedure, the ratio is m     k  dxf ( x) ... tk 

k 1 0  k  l sl1ts    dtl ul ( x,  ts ,t1,..., tl 1 ) exp(   ul ( x, , t1,...tl 1 )d ) , l 1  s1 l1    s1ts  ( / L) (required localization accuracy) 1  ( / L)  1 4  2  6    ( / L)   3  W3  ( / L)  L    where ui(x,t,t1,…,ti-1) is the function that sets the view window at the i-th stage, provided that the intervals recorded between the previous (i-1) pulses were respectively t1,t2,…,ti-1. It is not always possible to find extremals that deliver a minimum to the localization time ( 9 ) in the general case (when the probability density f(x) is arbitrary). Therefore, we have developed a universal procedure to search for a source in the case when there is no priori information about the intensity of the source (so, we can assume that the source has a uniform distribution over the search interval). Due to the limited scope of this message, only the resulting table summarizing the parameters of the optimal multistep search for a random uniformly distributed point source for systems with one receiver is given, and all necessary analytical and numerical calculations are omitted. More detailed information on this can be found in [9-10]. when (ε/L) → 0, we get the following asymptotic relations for systems with one receiver: mopt  ln(L /  );

Wi  ei  L, i  1, mopt ;   opt  e ln(L /  )  .

The results presented above are the set of speed-optimal algorithms to localize random pulsed-point sources using system with one receiver. The studies were carried out both for single-step search procedures (in the case of an    (average time of localization) 1 ( / L)1  2 ( / L)  12 

 1 ( / L) 3 3  m  ( / L)m1 arbitrary probability density of the random source distribution on the search interval) and for multi-stage localization algorithms (for those cases when a random point-impulse object has a uniform distribution on the search interval). Acknowledgements. This work was supported by the Russian Foundation for Basic Research (grants No. 19-01128 and 18-51-00001) and the Ministry of Science and Higher Education (Project No. AAA-A17-117052410034-6).

References

[1] J.H. Barnes , G.M. Hieftje . Recent Advances in Detector-Array Technology for Mass Spectrometry // Int. J. Mass Spectrom . 2004 . V. 238. P. 33 - 46 .

[2] V.S. Kirichuk , K. Yu.Mokin , and A.L. Reznik . Algorithms for Processing of Series of Digital Aerospace Images Based on Automatic Search for the Conjugate Points // Pattern Recognition and Image Analysis , 2001 , vol. 11 , No 1, pp. 192 - 194 .

[3] B.V. Gnedenko , Yu.K. Belyayev , and A.D. Solovyev , Mathematical Methods of Reliability Theory (Nauka , Moscow, 1965 ; Academic, New York, 1969 ).

[4] M. Mallick , V. Krishnamurthy , B. Vo . Integrated Tracking, Classification, and Sensor Management: Theory and Applications . Wiley, 2012 , 736 p.

[5] X. Zhu , L. Wen , G. Hobbs and oth. Detection and localization of single-source gravitational waves with pulsar timing arrays // M.N. of the Royal Astronomical Society , Oxford Academic Press, v. 449 , № 2 , 2015 , p. 1650 - 1663 .

[6] M.J.D. Powell . A Fast Algorithm for Nonlinearly Constrained Optimization Calculations . Numerical Analysis , G.A.Watson ed., Lecture Notes in Mathematics , Springer Verlag, Vol. 630 , 1978 .

[7] R.E. Bellman , I.L. Glicksberg , and O.A. Gross . Some aspects of the mathematical theory of control processes . Santa Monica, CA: RAND Corporation, 1958 , 263p .

[8] D. Bertsekas . Constrained optimization and Lagrange multiplier methods . New York: Academic Press. 1982 .

[9] A.L. Reznik , A.A. Solov 'ev, and A.V. Torgov . The algorithms of optimum localization of random pulsed-point source under the condition of its uniform distribution on a search interval // Pattern Recognition and Image Analysis . Advances in Mathematical Theory and Applications , 2018 , Vol. 28 , No. 2 , pp. 354 - 361 .

[10] A.L. Reznik , A.V. Tuzikov , A.A. Solov 'ev, and A.V. Torgov . Time-Optimal algorithms of searching for pulsed-point sources for systems with several detectors // Optoelectronics, Instrumentation and Data Processing , 2017 , Vol. 53 , Issue 3, pp. 203 - 209 .