# Which of an array's contiguous subarrays is an algorithm best applied to?

A function $$f$$ accepts two equally-long arrays $$A$$ and $$B$$ as input, and returns a real number $$s$$ such that the root mean square of $$A-sB$$ is minimal.

I'm hoping to come up with a better-than-brute-force approach to the following problem:

Given a pair of equally-long ($$n \sim 10^7$$) arrays $$C,D$$ of numbers from the interval $$[-1,1]\subset\mathbb{R}$$, how are array indices $$i,j$$ chosen that satisfy

a) $$j-i \gtrsim 10^4$$

b) $$s=f\left(C[i\dots j],D[i\dots j]\right)$$ is 'optimal', in the sense that if indices $$k,l$$ satisfy $$k\leq i, then

$$\text{RMS}(C[i\dots j]-sD[i\dots j]) \leq \text{RMS}(C[i\dots j]-s'D[i\dots j])$$

where $$s'=f\left(C[k\dots l],D[k\dots l]\right)$$.

(I'm hoping that by recursing on the subarrays to the left and right of these 'optimal' subarrays, the entirety of the pair of large arrays can be processed... 'optimally'.)

I'll be grateful for even a piece of jargon describing the abstract approach this is surely an instance of. Apologies for notational abuses and not-entirely-appropriate title - hope the point is clear.

As per GrapefruitIsAwesome's answer, solving the RMS problem is fairly trivial even with large arrays. The part with the subarrays seems equally trivial: If $$s$$ minimizes the RMS difference between $$C[i…j]$$ and $$D[i…j])$$ then

$$\text{RMS}(C[i\dots j]-sD[i\dots j]) \leq \text{RMS}(C[i\dots j]-s'D[i\dots j])$$

will always be true regardless of how you define $$s'$$. That's the whole point of "minimization": the RMS difference will be the smallest it can be.

• Am more than grateful for the razor-sharp clarity of your answer (even tho' my question seems especially trivial in light of it). Requirement a) came about because when C and D correspond to 'correlated' 96kHz audio (e.g. 2 channels of a surround track), audible glitches exist in the 'difference track' ("T") if samples are processed in too-small chunks. I see now thanks to you that there's no point employing chunks longer than this lower limit ("u"). I now wonder if RMS(T) depends much on whether f is fed [0...u-1], [u...2u-1],... vs (ignoring [0...u/2-1]) [u/2...3u/2-1], [3u/2...5u/2-1],... May 27, 2022 at 0:40

Let $$f(s) = \sqrt{\sum_{n=1}^{N} \left(A_n - s B_n\right)^2}$$

Find $$s$$ that minimizes $$f(s)$$

As the function is strictly positive we can square both sides without affecting the result so: $$g(s) = \left[f(s)\right]^2 = \sum_{n=1}^{N} \left(A_n - s B_n\right)^2$$

So minimizing $$g(s)$$ with respect to s will yield the same answer for $$s$$.

$$g(s) = \sum_{n=1}^{N} A_n^2 - 2s\sum_{n=1}^{N} A_nB_n + s^2\sum_{n=1}^{N} B_n^2$$

Now taking the derivative, and setting it equal to zero to minimize, then solving for $$s$$: $$\frac{d}{ds}g(s) = \frac{d}{ds}\sum_{n=1}^{N} A_n^2 - \frac{d}{ds}2s\sum_{n=1}^{N} A_nB_n + \frac{d}{ds}\sum_{n=1}^{N} B_n^2 = 0$$

$$0 - 2\sum_{n=1}^{N} A_nB_n + 2s\sum_{n=1}^{N} B_n^2 = 0$$

$$2s\sum_{n=1}^{N} B_n^2 = 2\sum_{n=1}^{N} A_nB_n$$

$$s = \frac{\sum_{n=1}^{N} A_nB_n}{\sum_{n=1}^{N} B_n^2}$$