# How to Approximate / Fit a Function and a Lower Bound on It?

I am dealing with a complicated optimization problem with two parameters $N, K$. Setting $K =$ constant and finding the minimum for different $N$'s lead to a set of function values. I can do this for $K = 2,3,\cdots,8$ and $N = 5,6,\cdots,40$. Larger $K$'s or $N$'s take more time to calculate (e.g. 1 hour).

I've plotted what I get (blue) and a lower bound (green) for it, which is described by $L(N,K) = \sqrt{\frac{N-K}{K(N-1)}}$

$K = 3$

$K = 4$

Any of these two are desired :

1. An expression with respect to $(N,K)$ which best approximates the values I'm getting.

2. A tighter lower bound (for larger $N$'s)

What methods do you suggest?

• Exact or least-squares polynomial interpolation are some methods that come to mind, at least without seeing a representative dataset. – Jason R Sep 20 '13 at 12:03
• It would be helpful if you give us the function you are trying to approximate. – jan Sep 20 '13 at 15:10
• In case the only parameters involved are $N, K$ then you can fit the data any way you want (Least squares, 1-Norm minimization methods are a few widely used ones). – Sudarsan Sep 20 '13 at 18:24
• This looks like the Welch bound problem (lower bound on the maximum magnitude of the aperiodic autocorrelation and cross-correlation functions of $K$ binary sequences of length $N$). Giving some context would have been helpful. – Dilip Sarwate Sep 21 '13 at 13:36
• It is conjectured that the blue curves are the exact minimum of maximum magnitude of cross-correlation of all columns of DFT sub-matrices of size $K\times N$. I want to see to what extent this conjecture is true? So finding a tighter lower bound for it is so useful! Also there is another one By Levenstein which is tighter than Welch one for $N>K^2$. – Mahdi Khosravi Sep 21 '13 at 14:33