ASAlexei Shadrin

Alexei Shadrin

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Alexei Shadrin has a total of 15 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Sparse Approximation and Sampling Recovery on Function Classes with a Structural Condition

    by A. Yu. Shadrin, V. N. Temlyakov, S. Yu. Tikhonov

    In nonlinear approximation, it is common to consider classes of functions given by their expansion coefficients with respect to some basis \(\Psi=(\psi_{\mathbf k})\), i.e., \(f = \sum_{\mathbf k\in\mathbb Z^d} a_{\mathbf k} \psi_{\mathbf k}\), with certain structural conditions imposed on the coefficients \((a_{\mathbf k})\) and certain conditions imposed on the basis \((\psi_{\mathbf k})\). A classical example is given by absolutely convergent series \(\sum_{\mathbf k\in\mathbb Z^d}\mathopen|a_{\mathbf k}|<\infty\) with respect to an orthogonal or a Riesz basis \((\psi_{\mathbf k})\), or even a redundant set of functions. Here, we study the classes of functions \(\mathbf A_\beta^{r,b}(\Psi,\mathcal G)\) with the property where the index sets \(\mathcal G=(G_j)\) satisfy \(G_{j-1}\subset G_j\) and \(\bigcup_{j=1}^\infty G_j = \mathbb Z^d\). It has been shown recently that universal sampling discretization and nonlinear sparse approximation are useful in the sampling recovery problem for this type of functions, namely, when \((G_j)\) are dyadic cubes or dyadic hyperbolic crosses. In this paper, we generalize these particular results to the classes of functions defined by index sets \((G_j)\) of a rather general structure.


  • Open Access

    On the cardinality of lower sets and universal discretization

    by F. Dai, A. Prymak, A. Shadrin, V. Temlyakov, S. Tikhonov

    A set $Q$ in $\mathbb{Z}_+^d$ is a lower set if $(k_1,\dots,k_d)\in Q$ implies $(l_1,\dots,l_d)\in Q$ whenever $0\le l_i\le k_i$ for all $i$. We derive new and refine known results regarding the cardinality of the lower sets of size $n$ in $\mathbb{Z}_+^d$. Next we apply these results for universal discretization of the $L_2$-norm of elements from $n$-dimensional subspaces of trigonometric polynomials generated by lower sets.

  • Open Access

    Fast and Stable Approximation of Analytic Functions from Equispaced Samples via Polynomial Frames

    by Ben Adcock, Alexei Shadrin

    We consider approximating analytic functions on the interval $$[-1,1]$$ [ - 1 , 1 ] from their values at a set of $$m+1$$ m + 1 equispaced nodes. A result of Platte, Trefethen & Kuijlaars states that fast and stable approximation from equispaced samples is generally impossible. In particular, any method that converges exponentially fast must also be exponentially ill-conditioned. We prove a positive counterpart to this ‘impossibility’ theorem. Our ‘possibility’ theorem shows that there is a well-conditioned method that provides exponential decay of the error down to a finite, but user-controlled tolerance $$\epsilon > 0$$ ϵ > 0 , which in practice can be chosen close to machine epsilon. The method is known as polynomial frame approximation or polynomial extensions. It uses algebraic polynomials of degree n on an extended interval $$[-\gamma ,\gamma ]$$ [ - γ , γ ] , $$\gamma > 1$$ γ > 1 , to construct an approximation on $$[-1,1]$$ [ - 1 , 1 ] via a SVD-regularized least-squares fit. A key step in the proof of our main theorem is a new result on the maximal behaviour of a polynomial of degree n on $$[-1,1]$$ [ - 1 , 1 ] that is simultaneously bounded by one at a set of $$m+1$$ m + 1 equispaced nodes in $$[-1,1]$$ [ - 1 , 1 ] and $$1/\epsilon $$ 1 / ϵ on the extended interval $$[-\gamma ,\gamma ]$$ [ - γ , γ ] . We show that linear oversampling, i.e. $$m = c n \log (1/\epsilon ) / \sqrt{\gamma ^2-1}$$ m = c n log ( 1 / ϵ ) / γ 2 - 1 , is sufficient for uniform boundedness of any such polynomial on $$[-1,1]$$ [ - 1 , 1 ] . This result aside, we also prove an extended impossibility theorem, which shows that such a possibility theorem (and consequently the method of polynomial frame approximation) is essentially optimal.


  • Open Access

    Fast and stable approximation of analytic functions from equispaced samples via polynomial frames

    by Ben Adcock, Alexei Shadrin

    We consider approximating analytic functions on the interval $[-1,1]$ from their values at a set of $m+1$ equispaced nodes. A result of Platte, Trefethen \& Kuijlaars states that fast and stable approximation from equispaced samples is generally impossible. In particular, any method that converges exponentially fast must also be exponentially ill-conditioned. We prove a positive counterpart to this `impossibility' theorem. Our `possibility' theorem shows that there is a well-conditioned method that provides exponential decay of the error down to a finite, but user-controlled tolerance $\epsilon > 0$, which in practice can be chosen close to machine epsilon. The method is known as \textit{polynomial frame} approximation or \textit{polynomial extensions}. It uses algebraic polynomials of degree $n$ on an extended interval $[-\gamma,\gamma]$, $\gamma > 1$, to construct an approximation on $[-1,1]$ via a SVD-regularized least-squares fit. A key step in the proof of our main theorem is a new result on the maximal behaviour of a polynomial of degree $n$ on $[-1,1]$ that is simultaneously bounded by one at a set of $m+1$ equispaced nodes in $[-1,1]$ and $1/\epsilon$ on the extended interval $[-\gamma,\gamma]$. We show that linear oversampling, i.e., $m = c n \log(1/\epsilon) / \sqrt{\gamma^2-1}$, is sufficient for uniform boundedness of any such polynomial on $[-1,1]$. This result aside, we also prove an extended impossibility theorem, which shows that such a possibility theorem (and consequently the method of polynomial frame approximation) is essentially optimal.

  • On Stable Reconstruction of Analytic Functions from Fourier Samples

    by S. V. Konyagin, A. Yu. Shadrin

    Stability of reconstruction of analytic functions from the values of \(2m+1\) coefficients of its Fourier series is studied. The coefficients can be taken from an arbitrary symmetric set \(\delta_{m}\subset\mathbb{Z}\) of cardinality \(2m+1\). It is known that, for \(\delta_{m}=\{j:|j|\leq m\}\), i.e., if the coefficients are consecutive, the fastest possible convergence rate in the case of stable reconstruction is an exponential function of the square root of \(m\). Any method with faster convergence is highly unstable. In particular, exponential convergence implies exponential ill-conditioning. In this paper we show that if the sets \((\delta_{m})\) are chosen freely, there exist reconstruction operators \((\phi_{\delta_{m}})\) that have exponential convergence rate and are almost stable; specifically, their condition numbers grow at most linearly: \(\kappa_{\delta_{m}}<c\,m\). We also show that this result cannot be noticeably strengthened. More precisely, for any sets \((\delta_{m})\) and any reconstruction operators \((\phi_{\delta_{m}})\), exponential convergence is possible only if \(\kappa_{\delta_{m}}\geq c\,m^{1/2}\).


  • Sampling Discretization of Integral Norms

    by F. Dai, A. Prymak, A. Shadrin, V. Temlyakov, S. Tikhonov


  • Open Access

    Об устойчивом восстановлении аналитических функций по выборке из коэффициентов ряда Фурье

    by С. В. Конягин, А. Ю. Шадрин

    УДК 519.651 + 517.518.454 + 517.518.86 MSC: 65D15, 41A10, 41A17, 42A16 DOI: 10.21538/0134-4889-2020-26-4-182-195 Работа выполнена первым автором при поддержке гранта Правительства Российской Федерации (проект 14.W03.31.0031). Рассматривается задача об устойчивости восстановления аналитической функции по значениям $2m+1$ коэффициентов ее ряда Фурье, которые могут быть взяты из

  • Open Access

    Entropy numbers and Marcinkiewicz-type discretization theorem

    by F. Dai, A. Prymak, A. Shadrin, V. Temlyakov, S. Tikhonov

    This paper studies the behavior of the entropy numbers of classes of functions with bounded integral norms from a given finite dimensional linear subspace. Upper bounds of these entropy numbers in the uniform norm are obtained and applied to establish a Marcinkiewicz type discretization theorem for integral norms of functions from a given finite dimensional subspace.

  • Open Access

    Sampling discretization of integral norms

    by F. Dai, A. Prymak, A. Shadrin, V. Temlyakov, S. Tikhonov

    The paper is devoted to discretization of integral norms of functions from a given finite dimensional subspace. Even though this problem is extremely important in applications, its systematic study has begun recently. In this paper we obtain a conditional theorem for all integral norms $L_q$, $1\le q<\infty$, which is an extension of known results for $q=1$. To discretize the integral norms successfully, we introduce a new technique, which is a combination of probabilistic technique with results on the entropy numbers in the uniform norm. As an application of the general conditional theorem, we derive a new Marcinkiewicz type discretization for the multivariate trigonometric polynomials with frequencies from the hyperbolic crosses.