## 2 Using Legendre Polynomials for Randomized Projection Estimates  
### Fourier-Legendre Series  
The standardized Legendre polynomials \(\{P_{i}\}_{i=0}^{\infty}\) are defined on the set \(\Omega=[-1,1]\) as follows [9]:  
\[P_{i}(x)=\frac{1}{2^{i}!}\,\frac{d^{i}(x^{2}-1)^{i}}{dx^{i}},\ \ \ i=0,1,2,\ldots\]  
They form a complete orthogonal system of functions in the space \(L_{2}(\Omega)\)[10], where  
\[L_{2}(\Omega)=\bigg{\{}u\colon\int_{\Omega}|u(x)|^{2}dx<\infty\bigg{\}},\]  
and satisfy well-known recurrence relations:  
\[(i+1)P_{i+1}(x)=(2i+1)xP_{i}(x)-iP_{i-1}(x),\ \ \ i=1,2,\ldots, \tag{1}\] \[(2i+1)P_{i}(x)=P_{i+1}^{\prime}(x)-P_{i-1}^{\prime}(x),\ \ \ i=1,2,\ldots, \tag{2}\]  
where \(P_{0}(x)=1\) and \(P_{1}(x)=x\). These relations can be formally applied for \(i=0\) when \(P_{-1}(x)=0\). The explicit formula for the standardized Legendre polynomials is  
\[P_{i}(x)=\frac{1}{2^{i}}\sum_{k=0}^{\lfloor i/2\rfloor}\frac{(-1)^{k}(2i-2k)! }{k!(i-k)!(i-2k)!}\,x^{i-2k},\ \ i=0,1,2,\ldots, \tag{3}\]  
where \(\lfloor\,\cdot\,\rfloor\) is the floor function. The explicit formulae can be specified separately for even indices (\(i=2j\)), as  
\[P_{2j}(x)=\frac{1}{2^{2j}}\sum_{k=0}^{j}\frac{(-1)^{k}(4j-2k)!}{k!(2j-k)!(2j-2 k)!}\,x^{2j-2k}, \tag{4}\]and for odd indices (\(i=2j+1\)), as  
\[P_{2j+1}(x)=\frac{1}{2^{2j+1}}\sum_{k=0}^{j}\frac{(-1)^{k}(4j-2k+2)!}{k!(2j-k+1)! (2j-2k+1)!}\,x^{2j-2k+1}. \tag{5}\]  
Using the normalization, we obtain the Legendre polynomials \(\{\hat{P}_{i}\}_{i=0}^{\infty}\) that form a complete orthonormal system of functions in \(L_{2}(\Omega)\):  
\[\hat{P}_{i}(x)=\sqrt{\frac{2i+1}{2}}\,P_{i}(x),\ \ \ i=0,1,2,\ldots \tag{6}\]  
The expansion of an arbitrary function \(u\in L_{2}(\Omega)\) into the Fourier-Legendre series has the form  
\[u(x)=\sum_{i=0}^{\infty}U_{i}\hat{P}_{i}(x), \tag{7}\]  
where coefficients \(U_{i}\) are defined as inner products, i.e.,  
\[U_{i}=(u,\hat{P}_{i})_{L_{2}(\Omega)}=\int_{\Omega}u(x)\hat{P}_{i}(x)dx,\ \ \ i=0,1,2,\ldots\]  
This expansion is a basis for the approximation of \(u\):  
\[L_{2}(\Omega)=\bigg{\{}u\colon\int_{\Omega}|u(x)|^{2}dx<\infty\bigg{\}},\]0  
and the approximation accuracy is estimated depending on the chosen metric (or norm). For example, in \(L_{2}(\Omega)\), we have [11]  
\[L_{2}(\Omega)=\bigg{\{}u\colon\int_{\Omega}|u(x)|^{2}dx<\infty\bigg{\}},\]1  
where \(C>0\) does not depend on \(n\), under the condition that the generalized derivatives of \(u\) up to order \(s\) belong to \(L_{2}(\Omega)\). There is also the sharper estimate [12; 13]  
\[L_{2}(\Omega)=\bigg{\{}u\colon\int_{\Omega}|u(x)|^{2}dx<\infty\bigg{\}},\]2  
for which it is assumed that \(\tilde{C}>0\) does not depend on \(n\), and the generalized derivatives of \(u\) up to order \(s\) belong to \(L_{2}(\Omega)\) with weight \(\rho(x)=(1-x^{2})^{s}\), \(s\leqslant n+1\). We also present the estimate corresponding to \(C(\Omega)\), the space of all continuous functions on \(\Omega\). If a function \(u\) is continuously differentiable \(r\) times on \(\Omega\), i.e., \(u\in C^{r}(\Omega)\), and its derivative \(u^{\langle r\rangle}\) satisfies the Lipschitz condition with parameter \(\alpha\in(0,1]\), then  
\[L_{2}(\Omega)=\bigg{\{}u\colon\int_{\Omega}|u(x)|^{2}dx<\infty\bigg{\}},\]3  
where \(\tilde{C}>0\) does not depend on \(n\), \(r+\alpha>1/2\)[9]. **Remark 1**. : _In inequality (9), the parameter \(s\) can be a real non-negative number [14]. In this case, we should use the condition \(u\in W^{s}_{2}(\Omega)\) for \(s\geqslant 0\) instead of the condition that the generalized derivatives of \(u\) up to order \(s\) belong to \(L_{2}(\Omega)\).