0
$\begingroup$

I'm trying to minimise a function of the form

$f(s)=\frac{1}{T}\sum^T_{t=1}(x_t-s_t)^2+\sum^T_{t=2}(s_t-s_{t-1})^2$, where the vector $x$ is fixed, and $T$ is of the order of $10^2$.

I've tried Minimize[f[s], {s}], but Mathematica assumes s is just a number and not a vector.

How do I minimize this?

$\endgroup$
  • 1
    $\begingroup$ Might consider using Indexed[] to formulate your objective function. $\endgroup$ – J. M.'s discontentment Oct 20 '18 at 12:58
3
$\begingroup$

This is more of a mathematics question rather than a Mathematica question, but I will answer with a bit of a Mathematica flavor.

Your function to be minimized can be written as:

$$v = \frac{1}{t} (x-s) \cdot (x-s) + s \cdot M \cdot s$$

where:

$$A = \left( \begin{array}{cccc} 1 & -1 \\ & 1 & -1 \\ & & \ddots & \ddots \\ & & & 1 & -1 \end{array} \right)$$

and

$$M = A^T \cdot A$$

The vector derivative with respect to $s$ is:

$$- \frac{2}{t} (x-s) + 2 M \cdot s$$

Setting this to $0$ yields:

$$(I + t M) \cdot s == x$$

where $I$ is the identity matrix. Hence, the minimum occurs at:

$$s = (I + t M)^{-1} \cdot x$$

Here is a function that computes the minimum for $x$:

A[dim_] := SparseArray[{Band[{1,1}]->1, Band[{1,2}]->-1}, {dim-1, dim}]
M[dim_] := Transpose[A[dim]] . A[dim]

mins[x_] := With[{dim = Length[x]},
    LinearSolve[IdentityMatrix[dim, SparseArray] + dim M[dim], x]
]

Example:

SeedRandom[1]
x = RandomReal[1, 5]
s = mins[x]

1/5 (x - s) . (x - s) + s . M[5] . s

{0.817389, 0.11142, 0.789526, 0.187803, 0.241361}

{0.506737, 0.444606, 0.449113, 0.385537, 0.361507}

0.0838865

Let's check this using ArgMin:

s = Array[t, 5];
ArgMin[1/5 (x - s) . (x - s) + s . M[5] . s, s]

{0.506737, 0.444606, 0.449113, 0.385537, 0.361507}

Larger example:

SeedRandom[2]
x = RandomReal[1, 100];
s = mins[x]; //AbsoluteTiming

1/100 (x - s) . (x - s) + s . M[100] . s

{0.000458, Null}

0.0693302

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ As an addendum to Carl's fabulous answer: the matrix $\mathbf M$ is a specially-structured tridiagonal matrix with known eigenstructure, which should allow for closed-form solutions for the components of the solution vector. $\endgroup$ – J. M.'s discontentment Oct 20 '18 at 16:48
  • $\begingroup$ Carl, thanks for your answer. I do think my question was more on the Mathematica than mathematics side, while your answer was more on the mathematics side. $\endgroup$ – An old man in the sea. Oct 20 '18 at 17:25
0
$\begingroup$

For future reference ( I used J.M. helpful comment).

HPo[lambda_, x_] := 
      1/T *Sum[(data[[i]] - Indexed[x, i])^2, {i, 1, T}] + 
       lambda/T*
        Sum[((Indexed[x, i + 1] - Indexed[x, i]) - (Indexed[x, i] - 
              Indexed[x, i - 1]))^2, {i, 2, T - 1}];
    hpdata = ArgMin[HPo[16, x], Table[Indexed[x, i], {i, 1, T}]];
| improve this answer | |
$\endgroup$
  • $\begingroup$ I know this is very inefficient, but it works for my purpose. $\endgroup$ – An old man in the sea. Oct 21 '18 at 23:37
  • $\begingroup$ You don't need the Table[] in ArgMin[]; ArgMin[HPo[16, x], x] should already work. $\endgroup$ – J. M.'s discontentment Oct 22 '18 at 5:05
  • $\begingroup$ @J.M.iscomputer-less I tried it, and It doesn't... $\endgroup$ – An old man in the sea. Oct 22 '18 at 8:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.