# How to detect a long signal inside an even longer one?

I'm trying to detect a long pattern inside a long recorded audio. In order to do so I am implementing a matched filter in time by performing a FIR filtering using the coefficients of my pattern inverted in time as filter coefficients and doing all the processing in frequency domain. I'm ensuring periodic convolution is equivalent to linear convolution by carefully selecting the FFT size named NFFT so that there's no time aliasing at the output.

$ifft(fft(patternCoeffTimeInverted,NFFT).*fft(Segment,NFFT),NFFT)$

I am familiar with the existence of overlap-add and overlap-save algorithms to optimally compute the FFTs I would use to implement the convolution between pattern and audio. The problem I'm facing is that normally these algorithms operate with a manageable number of filtering coefficients A and the large audio is divided into chunks of size B for easier processing. My question is what can I do if both the filtering coefficients and the audio are large? Would I have to nest overlap-adds by taking the first chunk of audio B and use it as coefficients A' in a second overlap-add while dividing the original coefficients from A into chunks just to have an output to be used in an iteration of the first overlap-add and then do this for every iteration of the first overlap-add?

• What is "long" for you, in number of samples and time? Jun 13 '18 at 1:19
• ping? This really sounds like an XY Problem, where you think you must solve the problem of an overly long convolution by hand, whilst almost all signal processing toolboxes offer automated acceleration of exactly that problem by themselves transparently. Which framework are you working in? How small is your computer that audio samples become a large problem? How much samples is "long", anyway? Jun 13 '18 at 9:30
• @MarcusMüller I would really appreciate if you were a little bit less aggressive while asking for more information. I'm working with Matlab. I have a computer with 10 GB of RAM and Matlab says "array exceeds maximum array size preference. Creation of arrays greater than this limit may take a long time and cause MATLAB to become unresponsive." Up to the point in which I say "My question is what can I do if both the filtering coefficients and the audio are large?" There's no XY problem. Answer up to that point and forget about the last paragraph if it makes you uncomfortable.
– VMMF
Jun 13 '18 at 16:01
• Wow, that is really much data, it seems, but the info that you're doing this in Matlab is useful to any potential answer (as it gives us information about the things you can't and can do in your environment). I'd still like to know the order of magnitude of samples you're dealing with. Note that this is relevant to my own interests, as we'll effectively be doing similar things on RF samples (order of magnitude of the shorter sequence: $10^6$ to $10^8$), and are really not expecting to run into the same issues. Jun 13 '18 at 16:18
• and: the fact that you're trying to solve a "matlab refuses to allocate an array large enough" problem actually shows it's kind of an XY problem: until you wrote that, it wasn't clear whether the problem was computation time, memory constraints, numerical stability of the FFTs of that size, or, and that's the case here, possibly, architectural constraints of the specific software you're using! Jun 13 '18 at 17:34

Using the matched filter is right approach and typically a full length filter should be used.

One of the advantages is that filter gain is approximately proportional to $10\log(T)$.

If you don’t need full gain you can use a chunk of your matched filter and still have acceptable detection performance.

One technique in active sonar is to use a broken up matched filters because returns tend to be broken up. A target isn’t a point reflector.

You can also use linearity and time invariance to break up the long convolution. Say take the first half of your matched filter and convolve it with your long time series. Then do the same with the second half matched filter. If you align the 2 convolved time series, offset by the length of the first half filter, adding the convolved time series is equivalent to convolution by the full matched filter

Knowing the order of magnitude of the data you are dealing with is a good start to troubleshooting your problem because it might be something to do with other things around your implementation of overlap add or save (OA,OS).

OA, OS will work for even the weakest of CPUs. It might appear to take ages but it will not fail in a "hard way". By "hard way" here, I am referring to algorithms that might include operations taking place over arrays that must be created and that happen to be $N^k$ (for example) in size. Where $N$ is the length of the data and $k \in \mathbb{Z}$. In that case, at least at first sight, the hardware becomes the limiting factor because the technique forces you to create these large data structures. OA, OS are not in that category.

By default, MATLAB has to bring everything in memory and the fact that you have large samples might not be leaving much space in memory for even moderate size intermediate matrices.

It is likely however that you can use memory mapped IO. This is basically buffered access to the contents of a file but abstracted in such a way that you (the end-user) don't have to deal with the buffering. The only thing that you "see" is some x. You can do a=x[0] and you will get the first sample, or you can do a=x[687543621] and get...whatever is in that index within the file. The OS will handle mapping the contents of the file.

MATLAB does have memory mapped IO but, I am not sure to what extent it is used "internally". So, if your samples are in MP4, MP3 or any other format, the decoder for that format may be working with the assumption that what you want returned is an array, even if that array is 6GB long.

So, you can check to see if there is an implementation of a progressive decoder for your format for MATLAB which you can use to retrieve frames from your long files in a step-by-step way. If one does not exist, then you might have to write a little bit of code that decodes the sample and then writes it back to the disk in a form that MATLAB can then process via memory mapped IO. Memory mapped IO itself, through MATLAB is a relatively straightforward thing to do.

Now, the performance penalty incured by disk IO in this case is minimal if you are only traversing the file one way. In that case, you see a flat CPU load (say, an average of 60%) denoting processing and when the index of the file is about to reach the end of the memory buffer you will be observing a spike as the next "page" of the file gets loaded in memory. Unfortunately, if your algorithm does a lot of random access in various points in the file per frame, then the disk IO timings might become the limiting factor.

But, again, just doing OA, OS should work fine with memory mapped IO, even for a moderate size machine if your performance expectations are reasonable.

Hope this helps.