Hybrid M-Sequence Method

## An extension of the m-sequence technique for the analysis of multi-input nonlinear systems

### In Advanced Methods of Physiological Systems Modeling, Volume III, ed. V. Z. Marmarelis. New York, Plenum. pp. 87-110 (1994)

#### Abstract

White-noise analysis and related methods of nonlinear systems identification describe a physical system's response to its input in terms of "kernels" of progressively higher orders. A popular analytic scheme in the laboratory uses a class of pseudorandom binary sequences, m-sequences, as a test signal. The m-sequence method has several advantages for investigating linear and nonlinear systems: ease of implementation, rapid calculation of system kernels, and a solid theoretical framework. One difficulty with this method for nonlinear analysis comes from the algebraic structure of m-sequences: linear and nonlinear terms can be confounded, especially in the analysis of systems with many inputs.

We have developed a modification of the m-sequence method which allows control of these anomalies. This method is based on input signals consisting of a superposition of m-sequences whose lengths are relatively prime. The fast computational methods which facilitate kernel calculation for a single m-sequence input are readily extended to this new setting. We describe the theoretical foundation of this method and present an application to the study of ganglion cells of the macaque retina.
top nutshell diagram technotes background reading

#### The algorithm in a (large) nutshell

##### Inputs
The system is presented with signal s[1](t) at input 1, and signal s[2](t) at input 2. s[1](t) and s[2](t) are each derived from two m-sequences, m[1](t) and m[2](t), whose repeat periods M1 and M2 are relatively prime:
s[1](t) = m[1](t) + m[2](t)

and
s[2](t) = m[1](t+T1) + m[2](t+T2).

##### First-order kernels

To estimate the first-order kernels, cross-correlate the response R(t) against the m-sequence m[1](t):

C1(t) = < R(u)m[1](u-t) >.

• Beginning at t = 0, the cross-correlation C1(t) contains an estimate h^1[1](t) of the first-order kernel h[1](t) with respect to the first input.
• Beginning at t = T1, the cross-correlation C1(t) contains an estimate h^1[2](t) of the first-order kernel h[2](t) with respect to the second input.
An independent estimate of each of these kernels, h^2[1] and h^2[2], can be derived from the crosscorrelation of the response R(t) against the m-sequence m[2](t):
C2(t) = < R(u)m[2](u-t) >.

##### Second-order self- and cross-kernels

To estimate the second-order kernels, cross-correlate the response R(t) against the product of the underlying m-sequences m[1](t) and m[1](t):

C1,2(t[1],t[2]) = < R(u)m[1](u-t[1])m[2](u-t[2]) >.

As diagrammed below, the cross-correlation C1,2 contains estimates of the second-order kernels with respect to each input, as well as the second-order cross-kernel.
• Beginning at (t[1],t[2]) = (0,0), C1,2(t[1],t[2]) contains an estimate h^1,2[1,1](t[1],t[2]) of the second-order self-kernel h[1,1](t[1],t[2]) with respect to the first input.
• Beginning at (t[1],t[2]) = (T1,T2), C1,2(t[1],t[2]) contains an estimate h^1,2[2,2](t[1],t[2]) of the second-order self-kernel h[2,2](t[1],t[2]) with respect to the second input.
• Beginning at (t[1],t[2]) = (0,T2), C1,2(t[1],t[2]) contains an estimate h^1,2[1,2](t[1],t[2]) of the second-order cross-kernel h[1,2](t[1],t[2]).
• Beginning at (t[1],t[2]) = (T1,0), C1,2(t[1],t[2]) contains an independent estimate h^1,2[2,1](t[1],t[2]) of the second-order cross-kernel h[2,1](t[1],t[2]). Note that h[2,1](t[1],t[2]) = h[1,2](t[2],t[1]).

top nutshell diagram technotes background reading

#### Diagrammatic view of the algorithm for second-order kernels

This diagrams estimation of second-order kernels for a system with two inputs. Responses at eact time t are placed into the two dimensional array on the left, in a position corresponding to the position of signal with respect to its component m-sequences. That is, the response R(t) is positioned at (t1,t2), where
t1 = t (mod M1)
and
t2 = t (mod M2).

The cross-correlation
C1,2(t[1],t[2]) = < R(u)m[1](u-t[1])m[2](u-t[2]) >.

can be calculated by applying the fast m-transform sequentially along each axis. The transformed space (right panel) contains estimates of the second-order self- and cross-kernels.

The key to the algorithm is that because the m-sequence lengths M1 and M2 are relatively prime, all pairs of values of t1 and t2 occur exactly once, as t ranges from 0 to M1M2 - 1. This allows encoding of a function of two times (i.e., the second order-kernels) within a function of one time (the cross-correlation). It also allows us to "factor" the calculation of the cross-correlation into two stages.
top nutshell diagram technotes background reading

#### Technical notes

• Variants of the inverse-repeat method should be used to help remove higher-order "contaminants" from the kernel estimates.
• This approach is not limited to only two inputs. Each input is provided with a signal s[j](t), with distinct taps (e.g., spaced by T1 and T2) into each of the underlying m-sequences. The practical limit to the number of inputs is determined by the ratio of the shortest m-sequence length to the minimum tap separation (which is the anticipated timespan of the kernels).
• In principle, this approach is not limited to second-order kernels. For estimation of kth-order kernels, the analogous procedure relies on k m-sequences, each of relatively prime length. Each input is a sum of these k sequences, and has a repeat length equal to the product of the repeat lengths of the underlying m-sequences. For more than two inputs, additional taps in each sequence (beyond the two taps 0 and Tj for each sequence mj) should be used.
• Other nearly shift-orthogonal sequences besides m-sequences can be used, to avoid restrictions due to the limited set of repeat periods (7, 15, 31, 63, etc.) provided by m-sequences. Such sequences can be constructed for any length of form p = 4n-1, from the sequences of quadratic residues (mod p). However, the fast m-transform cannot be used to calculate cross-correlations with respect to these sequences.

top nutshell diagram technotes background reading

#### Background reading on m-sequences

Victor, J.D. (1992) Nonlinear systems analysis in vision: overview of kernel methods. In Nonlinear Vision: Determination of Neural Receptive Fields, Function, and Networks, ed. R. Pinter and B. Nabet. Cleveland, CRC Press. pp. 1-37.
##### The m-sequence method and the inverse-repeat idea
Sutter, E.E. (1987) A practical nonstochastic approach to nonlinear time-domain analysis. In Advanced Methods in Physiological System Modelling. Vol.1. ed. V. Z. Marmarelis. Los Angeles, Univ. of Southern California. pp. 303-315.
##### The fast m-transform
Sutter, E.E. (1991) The fast m-transform: a fast computation of cross-correlation with binary m-sequences. SIAM J. Comput. 20, 686-694.
top nutshell diagram technotes background reading

Download as pdf
Receptive field mapping with m-sequences
Dynamics of bipolar cells explored with m-sequences
Generalized orthogonal kernels and Wiener expansions
Publications related to receptive field analysis
Return to publications list