Alexei Shadrin
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
Research Subjects
Research Interests
Alexei Shadrin has a total of 15 co-authors. Here are the top co-authors by number of shared publications:
- Geno Nikolov
Faculty of Mathematics and Informatics, Sofia University, “St Kliment Ohridski”, Sofia, Bulgaria
6 shared publications - Sergey Tikhonov
Centre de Recerca Matemàtica, Barcelona, Spain
5 shared publications - Andriy Prymak
University of Manitoba
4 shared publications - Feng Dai
Department of Mathematical and Statistical Sciences, University of Alberta, Edmonton, Canada
4 shared publications - Vladimir N. Temlyakov
University of South Carolina, Columbia, USA
4 shared publications - Simon Foucart
Vanderbilt University
2 shared publications
Latest Publications
- 1 December 2025
- Published by Pleiades Publishing Ltd in Proceedings of the Steklov Institute of Mathematics
- Vol. 331 (1) , 270-283
Sparse Approximation and Sampling Recovery on Function Classes with a Structural Condition
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.- 1 December 2025
- Published by Pleiades Publishing Ltd in Proceedings of the Steklov Institute of Mathematics
- Vol. 331 (1) , 270-283
Sparse Approximation and Sampling Recovery on Function Classes with a Structural Condition
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
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 AccessOn the cardinality of lower sets and universal discretization
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
- 12 October 2022
- Published by Springer Nature in Constructive Approximation
- Vol. 57 (2) , 257-294
Fast and Stable Approximation of Analytic Functions from Equispaced Samples via Polynomial Frames
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 polynomial frame approximation or 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.- 12 October 2022
- Published by Springer Nature in Constructive Approximation
- Vol. 57 (2) , 257-294
Open AccessFast and Stable Approximation of Analytic Functions from Equispaced Samples via Polynomial Frames
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 polynomial frame approximation or 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. - Open Access
Fast and stable approximation of analytic functions from equispaced samples via polynomial frames
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.Open AccessFast and stable approximation of analytic functions from equispaced samples via polynomial frames
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. - 1 December 2021
- Published by Pleiades Publishing Ltd in Proceedings of the Steklov Institute of Mathematics
- Vol. 315 (S1) , S178-S191
On Stable Reconstruction of Analytic Functions from Fourier Samples
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}\).- 1 December 2021
- Published by Pleiades Publishing Ltd in Proceedings of the Steklov Institute of Mathematics
- Vol. 315 (S1) , S178-S191
On Stable Reconstruction of Analytic Functions from Fourier Samples
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}\).- 1 November 2021
- Published by Elsevier in Journal of Approximation Theory
- Vol. 271
Markov-type inequalities and extreme zeros of orthogonal polynomials
- 1 November 2021
- Published by Elsevier in Journal of Approximation Theory
- Vol. 271
Markov-type inequalities and extreme zeros of orthogonal polynomials
- 8 April 2021
- Published by Springer Nature in Constructive Approximation
- Vol. 54 (3) , 455-471
Sampling Discretization of Integral Norms
- 8 April 2021
- Published by Springer Nature in Constructive Approximation
- Vol. 54 (3) , 455-471
Sampling Discretization of Integral Norms
- Open Access
- 1 December 2020
- Published by Krasovskii Institute of Mathematics and Mechanics UB RAS in Trudy Instituta Matematiki i Mekhaniki UrO RAN
- Vol. 26 (4) , 182-195
Об устойчивом восстановлении аналитических функций по выборке из коэффициентов ряда Фурье
УДК 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$ коэффициентов ее ряда Фурье, которые могут быть взяты из- 1 December 2020
- Published by Krasovskii Institute of Mathematics and Mechanics UB RAS in Trudy Instituta Matematiki i Mekhaniki UrO RAN
- Vol. 26 (4) , 182-195
Open AccessОб устойчивом восстановлении аналитических функций по выборке из коэффициентов ряда Фурье
УДК 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
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 AccessEntropy numbers and Marcinkiewicz-type discretization theorem
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
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.Open AccessSampling discretization of integral norms
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.