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]
]

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

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

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

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