We investigate the universal approximation property (UAP) of transformer-type architectures, providing a unified theoretical framework that extends prior results on residual networks to models incorporating attention mechanisms. Our work identifies token distinguishability as a fundamental requirement for UAP and introduces a general sufficient condition that applies to a broad class of architectures. Leveraging an analyticity assumption on the attention layer, we can significantly simplify the verification of this condition, providing a non-constructive approach in establishing UAP for such architectures. We demonstrate the applicability of our framework by proving UAP for transformers with various attention mechanisms, including kernel-based and sparse ones. The corollaries of our results either generalize prior works or establish UAP for architectures not previously covered. Furthermore, our framework offers a principled foundation for designing novel transformer architectures with inherent UAP guarantees, including those with specific functional symmetries. We propose examples to illustrate these insights.

Abstract. Image restoration is critical across many fields, as it addresses the challenge of recovering clear images from degraded data. Two prominent approaches to this problem are wavelet-based methods and partial differential equation (PDE) models. Wavelet methods can be viewed as discrete analogs of PDE models, and through asymptotic analysis, wavelet models often converge to PDE-based approaches such as the total variation model. Wavelet methods are known for their simple implementation and multiscale time-frequency analysis, while PDE models provide a geometric interpretation of image structures, particularly edges. The relationship between these two approaches offers a comprehensive framework for image restoration. This paper designs a wavelet frame-based image restoration model, focusing on enhancing edge preservation and regularity. More importantly, we establish a connection to the [Formula: see text] version of the Mumford–Shah model, showing that the wavelet model converges to this variational model. This connection is significant, as it combines the geometric explanation of edges in the Mumford–Shah model with the simplicity of wavelet-based implementation. The primary contribution of this paper lies in the asymptotic analysis and proof of convergence of the two-scale wavelet model to the [Formula: see text] Mumford–Shah model, providing both theoretical insights and practical wavelet models for image restoration with enhanced edge detection.

We study the approximation of functions which are invariant with respect to certain permutations of the input indices using flow maps of dynamical systems. Such invariant functions include the much studied translation-invariant ones involving image tasks, but also encompasses many permutation-invariant functions that find emerging applications in science and engineering. We prove sufficient conditions for universal approximation of these functions by a controlled dynamical system, which can be viewed as a general abstraction of deep residual networks with symmetry constraints. These results not only imply the universal approximation for a variety of commonly employed neural network architectures for symmetric function approximation, but also guide the design of architectures with approximation guarantees for applications involving new symmetry requirements.

One of the arguments to explain the success of deep learning is the powerful approximation capacity of deep neural networks. Such capacity is generally accompanied by the explosive growth of the number of parameters, which, in turn, leads to high computational costs. It is of great interest to ask whether we can achieve successful deep learning with a small number of learnable parameters adapting to the target function. From an approximation perspective, this paper shows that the number of parameters that need to be learned can be significantly smaller than people typically expect. First, we theoretically design ReLU networks with a few learnable parameters to achieve an attractive approximation. We prove by construction that, for any Lipschitz continuous function $f$ on $[0,1]^d$ with a Lipschitz constant $\lambda>0$, a ReLU network with $n+2$ intrinsic parameters (those depending on $f$) can approximate $f$ with an exponentially small error $5 \lambda \sqrt{d} \, 2^{-n}$. Such a result is generalized to generic continuous functions. Furthermore, we show that the idea of learning a small number of parameters to achieve a good approximation can be numerically observed. We conduct several experiments to verify that training a small part of parameters can also achieve good results for classification problems if other parameters are pre-specified or pre-trained from a related problem.

This paper proposes a new neural network architecture by introducing an additional dimension called height beyond width and depth. Neural network architectures with height, width, and depth as hyper-parameters are called three-dimensional architectures. It is shown that neural networks with three-dimensional architectures are significantly more expressive than the ones with two-dimensional architectures (those with only width and depth as hyper-parameters), e.g., standard fully connected networks. The new network architecture is constructed recursively via a nested structure, and hence we call a network with the new architecture nested network (NestNet). A NestNet of height $s$ is built with each hidden neuron activated by a NestNet of height $\le s-1$. When $s=1$, a NestNet degenerates to a standard network with a two-dimensional architecture. It is proved by construction that height-$s$ ReLU NestNets with $\mathcal{O}(n)$ parameters can approximate $1$-Lipschitz continuous functions on $[0,1]^d$ with an error $\mathcal{O}(n^{-(s+1)/d})$, while the optimal approximation error of standard ReLU networks with $\mathcal{O}(n)$ parameters is $\mathcal{O}(n^{-2/d})$. Furthermore, such a result is extended to generic continuous functions on $[0,1]^d$ with the approximation error characterized by the modulus of continuity. Finally, we use numerical experimentation to show the advantages of the super-approximation power of ReLU NestNets.

Discretization invariant learning aims at learning in the infinite-dimensional function spaces with the capacity to process heterogeneous discrete representations of functions as inputs and/or outputs of a learning model. This paper proposes a novel deep learning framework based on integral autoencoders (IAE-Net) for discretization invariant learning. The basic building block of IAE-Net consists of an encoder and a decoder as integral transforms with data-driven kernels, and a fully connected neural network between the encoder and decoder. This basic building block is applied in parallel in a wide multi-channel structure, which is repeatedly composed to form a deep and densely connected neural network with skip connections as IAE-Net. IAE-Net is trained with randomized data augmentation that generates training data with heterogeneous structures to facilitate the performance of discretization invariant learning. The proposed IAE-Net is tested with various applications in predictive data science, solving forward and inverse problems in scientific computing, and signal/image processing. Compared with alternatives in the literature, IAE-Net achieves state-of-the-art performance in existing applications and creates a wide range of new applications where existing methods fail.

This paper develops simple feed-forward neural networks that achieve the universal approximation property for all continuous functions with a fixed finite number of neurons. These neural networks are simple because they are designed with a simple, computable, and continuous activation function $\sigma$ leveraging a triangular-wave function and the softsign function. We first prove that $\sigma$-activated networks with width $36d(2d+1)$ and depth $11$ can approximate any continuous function on a $d$-dimensional hypercube within an arbitrarily small error. Hence, for supervised learning and its related regression problems, the hypothesis space generated by these networks with a size not smaller than $36d(2d+1)\times 11$ is dense in the continuous function space $C([a,b]^d)$ and therefore dense in the Lebesgue spaces $L^p([a,b]^d)$ for $p\in [1,\infty)$. Furthermore, we show that classification functions arising from image and signal classification are in the hypothesis space generated by $\sigma$-activated networks with width $36d(2d+1)$ and depth $12$ when there exist pairwise disjoint bounded closed subsets of $\mathbb{R}^d$ such that the samples of the same class are located in the same subset. Finally, we use numerical experimentation to show that replacing the rectified linear unit (ReLU) activation function by ours would improve the experiment results.

A new network with super-approximation power is introduced. This network is built with Floor (⌊x⌋) or ReLU (max{0,x}) activation function in each neuron; hence, we call such networks Floor-ReLU networks. For any hyperparameters N∈N+ and L∈N+, we show that Floor-ReLU networks with width max{d,5N+13} and depth 64dL+3 can uniformly approximate a Hölder function f on [0,1]d with an approximation error 3λdα/2N-αL, where α∈(0,1] and λ are the Hölder order and constant, respectively. More generally for an arbitrary continuous function f on [0,1]d with a modulus of continuity ωf(·), the constructive approximation rate is ωf(dN-L)+2ωf(d)N-L. As a consequence, this new class of networks overcomes the curse of dimensionality in approximation power when the variation of ωf(r) as r→0 is moderate (e.g., ωf(r)≲rα for Hölder continuous functions), since the major term to be considered in our approximation rate is essentially d times a function of N and L independent of d within the modulus of continuity.

Despite its empirical success and recent theoretical progress, there generally lacks a quantitative analysis of the effect of batch normalization (BN) on the convergence and stability of gradient descent. In this paper, we provide such an analysis on the simple problem of ordinary least squares (OLS), where the precise dynamical properties of gradient descent (GD) is completely known, thus allowing us to isolate and compare the additional effects of BN. More precisely, we show that unlike GD, gradient descent with BN (BNGD) converges for arbitrary learning rates for the weights, and the convergence remains linear under mild conditions. Moreover, we quantify two different sources of acceleration of BNGD over GD – one due to over-parameterization which improves the effective condition number and another due having a large range of learning rates giving rise to fast descent. These phenomena set BNGD apart from GD and could account for much of its robustness properties. These findings are confirmed quantitatively by numerical experiments, which further show that many of the uncovered properties of BNGD in OLS are also observed qualitatively in more complex supervised learning problems.

The mutual intensity and its equivalent phase-space representations quantify an optical field's state of coherence and are important tools in the study of light propagation and dynamics, but they can only be estimated indirectly from measurements through a process called coherence retrieval, otherwise known as phase-space tomography. As practical considerations often rule out the availability of a complete set of measurements, coherence retrieval is usually a challenging high-dimensional ill-posed inverse problem. In this paper, we propose a trace-regularized optimization model for coherence retrieval and a provably convergent adaptive accelerated proximal gradient algorithm for solving the resulting problem. Applying our model and algorithm to both simulated and experimental data, we demonstrate an improvement in reconstruction quality over previous models as well as an increase in convergence speed compared to existing first-order methods.

In recent years, sparse coding has been widely used in many applications ranging from image processing to pattern recognition. Most existing sparse coding based applications require solving a class of challenging non-smooth and non-convex optimization problems. Despite the fact that many numerical methods have been developed for solving these problems, it remains an open problem to find a numerical method which is not only empirically fast, but also has mathematically guaranteed strong convergence. In this paper, we propose an alternating iteration scheme for solving such problems. A rigorous convergence analysis shows that the proposed method satisfies the global convergence property: the whole sequence of iterates is convergent and converges to a critical point. Besides the theoretical soundness, the practical benefit of the proposed method is validated in applications including image restoration and recognition. Experiments show that the proposed method achieves similar results with less computation when compared to widely used methods such as K-SVD.

Ultrasound video segmentation is a challenging task due to low contrast, shadow effects, complex noise statistics, and the need for high precision and efficiency in real time applications such as operation navigation and therapy planning. In this paper, we propose a wavelet frame based video segmentation framework incorporating different noise statistics and sequential distance shape priors. The proposed individual frame nonconvex segmentation model is solved by a proximal alternating minimization algorithm, and the convergence of the scheme is established based on the recently proposed Kurdyka--Łojasiewicz property. The performance of the overall method is demonstrated through numerical results on two real ultrasound video data sets. The proposed method is shown to achieve better results compared to the related level sets models and edge indicator shape priors, in terms of both segmentation quality and computational time.

Sparse coding and dictionary learning have seen their applications in many vision tasks, which usually is formulated as a non-convex optimization problem. Many iterative methods have been proposed to tackle such an optimization problem. However, it remains an open problem to have a method that is not only practically fast but also is globally convergent. In this paper, we proposed a fast proximal method for solving ℓ0norm based dictionary learning problems, and we proved that the whole sequence generated by the proposed method converges to a stationary point with sub-linear convergence rate. The benefit of having a fast and convergent dictionary learning method is demonstrated in the applications of image recovery and face recognition.

Respiration-correlated CBCT, commonly called 4DCBCT, provides respiratory phase-resolved CBCT images. A typical 4DCBCT represents averaged patient images over one breathing cycle and the fourth dimension is actually breathing phase instead of time. In many clinical applications, it is desirable to obtain true 4DCBCT with the fourth dimension being time, i.e., each constituent CBCT image corresponds to an instantaneous projection. Theoretically it is impossible to reconstruct a CBCT image from a single projection. However, if all the constituent CBCT images of a 4DCBCT scan share a lot of redundant information, it might be possible to make a good reconstruction of these images by exploring their sparsity and coherence/redundancy. Though these CBCT images are not completely time resolved, they can exploit both local and global temporal coherence of the patient anatomy automatically and contain much more temporal variation information of the patient geometry than the conventional 4DCBCT. We propose in this work a computational model and algorithms for the reconstruction of this type of semi-time-resolved CBCT, called cine-CBCT, based on low rank approximation that can utilize the underlying temporal coherence both locally and globally, such as slow variation, periodicity or repetition, in those cine-CBCT images.

We address the problem of reconstructing and analyzing surveillance videos using compressive sensing. We develop a new method that performs video reconstruction by low rank and sparse decomposition adaptively. Background subtraction becomes part of the reconstruction. In our method, a background model is used in which the background is learned adaptively as the compressive measurements are processed. The adaptive method has low latency, and is more robust than previous methods. We will present experimental results to demonstrate the advantages of the proposed method.

When taking pictures using a commodity camera in a scene with strong or harsh lighting, such as a sunny day outdoors, we often see a loss of highlight details (overexposure) in some bright regions and a loss of shadow details (underexposure) in some dark regions. In this paper, we develop a wavelet tight frame--based approach to reconstruct a well-exposed image with better visibility of details than that with over-/underexposed regions. There are two modules in the proposed approach: one in lightness channels that inpaints the clipped lightness and adjusts image contrast, and the other in chromatic channels that inpaints the saturated color regions. The experiments show that our method can effectively repair over-/underexposed regions, and it performs better than other existing methods on tested real photographs.

Wavelet frames have been successfully applied to various image restoration problems, such as denoising, inpainting, and deblurring. However, they are rarely used in geometric applications, except for the recent work of [B. Dong, A. Chien, and Z. Shen, Commun. Math. Sci., 9 (2011), pp. 551--559; B. Dong and Z. Shen, in Proceedings of the SPIE, Vol. 8401, 2012, 840102]. Motivated by the theoretical connection between wavelet frame based and total variation based image restoration models recently established in [J.-F. Cai, B. Dong, S. Osher, and Z. Shen, J. Amer. Math. Soc., 25 (2012), pp. 1033--1089], we propose here a convex multiphase segmentation model based on wavelet frame transform. The proposed model allows us to automatically identify complex tubular structures, including blood vessels, leaf vein systems, etc. Numerical results show that our method can extract more details than existing variational methods especially when the image contains different scales of structures. The proposed method is parallelized, and its efficiency is further improved by a graphics processing unit implementation. In addition, we analyze the connection between solutions of the convexified model and the original binary constrained model.

How to recover a clear image from a single motion-blurred image has long been a challenging open problem in digital imaging. In this paper, we focus on how to recover a motion-blurred image due to camera shake. A regularization-based approach is proposed to remove motion blurring from the image by regularizing the sparsity of both the original image and the motion-blur kernel under tight wavelet frame systems. Furthermore, an adapted version of the split Bregman method is proposed to efficiently solve the resulting minimization problem. The experiments on both synthesized images and real images show that our algorithm can effectively remove complex motion blurring from natural images without requiring any prior information of the motion-blur kernel.

This paper presents a new patch-based video restoration scheme. By grouping similar patches in the spatiotemporal domain, we formulate the video restoration problem as a joint sparse and low-rank matrix approximation problem. The resulting nuclear norm and $\ell_1$ norm related minimization problem can also be efficiently solved by many recently developed numerical methods. The effectiveness of the proposed video restoration scheme is illustrated on two applications: video denoising in the presence of random-valued noise, and video in-painting for archived films. The numerical experiments indicate that the proposed video restoration method compares favorably against many existing algorithms.

Frame-based image restoration by using the balanced approach has been developed over the last decade. Many recently developed algorithms for image restoration can be viewed as an acceleration of the proximal forward-backward splitting algorithm. Accelerated proximal gradient (APG) algorithms studied by Nesterov, Nemirovski, and others have been demonstrated to be efficient in solving various regularized convex optimization problems arising in compressed sensing, machine learning, and control. In this paper, we adapt the APG algorithm to solve the $\ell_1$-regularized linear least squares problem in the balanced approach in frame-based image restoration. This algorithm terminates in $O(1/\sqrt{\epsilon})$ iterations with an $\epsilon$-optimal solution, and we demonstrate that this single algorithmic framework can universally handle several image restoration problems, such as image deblurring, denoising, inpainting, and cartoon-texture decomposition. Our numerical results suggest that the APG algorithms are efficient and robust in solving large-scale image restoration problems. The algorithms we implemented are able to restore $512\times512$ images in various image restoration problems in less than 50 seconds on a modest PC. We also compare the numerical performance of our proposed algorithms applied to image restoration problems by using one frame-based system with that by using cartoon and texture systems for image deblurring, denoising, and inpainting.

Most existing video denoising algorithms assume a single statistical model of image noise, e.g. additive Gaussian white noise, which often is violated in practice. In this paper, we present a new patch-based video denoising algorithm capable of removing serious mixed noise from the video data. By grouping similar patches in both spatial and temporal domain, we formulate the problem of removing mixed noise as a low-rank matrix completion problem, which leads to a denoising scheme without strong assumptions on the statistical properties of noise. The resulting nuclear norm related minimization problem can be efficiently solved by many recently developed methods. The robustness and effectiveness of our proposed denoising algorithm on removing mixed noise, e.g. heavy Gaussian noise mixed with impulsive noise, is validated in the experiments and our proposed approach compares favorably against some existing video denoising algorithms.

Restoring a clear image from a single motion-blurred image due to camera shake has long been a challenging problem in digital imaging. Existing blind deblurring techniques either only remove simple motion blurring, or need user interactions to work on more complex cases. In this paper, we present an approach to remove motion blurring from a single image by formulating the blind blurring as a new joint optimization problem, which simultaneously maximizes the sparsity of the blur kernel and the sparsity of the clear image under certain suitable redundant tight frame systems (curvelet system for kernels and framelet system for images). Without requiring any prior information of the blur kernel as the input, our proposed approach is able to recover high-quality images from given blurred images. Furthermore, the new sparsity constraints under tight frame systems enable the application of a fast algorithm called linearized Bregman iteration to efficiently solve the proposed minimization problem. The experiments on both simulated images and real images showed that our algorithm can effectively removing complex motion blurring from nature images.

One promising approach to remove motion deblurring is to recover one clear image using an image pair. Existing dual-image methods require an accurate image alignment between the image pair, which could be very challenging even with the help of user interactions. Based on the observation that typical motion-blur kernels will have an extremely sparse representation in the redundant curvelet system, we propose a new minimization model to recover a clear image from the blurred image pair by enhancing the sparsity of blur kernels in the curvelet system. The sparsity prior on the motion-blur kernels improves the robustness of our algorithm to image alignment errors and image formation noise. Also, a numerical method is presented to efficiently solve the resulted minimization problem. The experiments showed that our proposed algorithm is capable of accurately estimating the blur kernels of complex camera motions with low requirement on the accuracy of image alignment, which in turn led to a high-quality recovered image from the blurred image pair.

Image classification often relies on texture characterization. Yet texture characterization has so far rarely been based on a true 2D multifractal analysis. Recently, a 2D wavelet Leader based multifractal formalism has been proposed. It allows to perform an accurate, complete and low computational and memory costs multifractal characterization of textures in images. This contribution describes the first application of such a formalism to a real large size (publicly available) image database, consisting of 25 classes of non traditional textures, with 40 high resolution images in each class. Multifractal attributes are estimated from each image and used as classification features within a standard k nearest neighbor classification procedure. The results reported here show that this Leader based multifractal analysis enables the effective discrimination of different textures, as performances in both classification scores and computational costs compare favorably against those of procedures previously proposed in the literature on the same database.

Real images usually have sparse approximations under some tight frame systems derived from framelets, an oversampled discrete (window) cosine, or a Fourier transform. In this paper, we propose a method for image deblurring in tight frame domains. It is reduced to finding a sparse solution of a system of linear equations whose coefficient matrix is rectangular. Then, a modified version of the linearized Bregman iteration proposed and analyzed in [J.-F. Cai, S. Osher, and Z. Shen, Math. Comp., to appear, UCLA CAM Report (08-52), 2008; J.-F. Cai, S. Osher, and Z. Shen, Math. Comp., to appear, UCLA CAM Report (08-06), 2008; S. Osher et al., UCLA CAM Report (08-37), 2008; W. Yin et al., SIAM J. Imaging Sci., 1 (2008), pp. 143–168] can be applied. Numerical examples show that the method is very simple to implement, robust to noise, and effective for image deblurring.

We compare, both objectively and subjectively, the performance of various advanced motion compensation methods, including overlapped block motion compensation (OBMC) and control grid interpolation (CGI), in a 3-D wavelet-based coding system. The motion vectors of the methods are obtained by using a sequence of 1-D dynamic programming algorithms that minimizes the cost function. Our experiment results indicate that an OBMC sequence usually has a higher peak signal-to-noise ratio (PSNR) than other methods, while a CGI sequence usually contains the fewest blocking artifacts. We provide a simple framework that combines the OBMC and CGI sequences. The proposed hybrid method removes more than 50% of the blocking artifacts of an OBMC sequence, while simultaneously maintaining a high PSNR performance.

Video clip consists of frames, and each frame can be considered as a transformed picture of the reference frame. In this paper, we briefly discuss a framelet method for high-resolution image reconstruction to enhance the resolution of video clips. The detailed discussion can be found in R.H. Chan et al. (2005). Experiments on an actual video clip show that our method can provide information that are not discernable from the given video clip.

This paper describes a new 3-D framework for the construction of a hybrid motion compensation model to reduce blocking artifacts in a highly scalable video coding system. Previous works have focused primarily on using control grid interpolation (CGI) or over-lapped block motion compensation (OBMC) to reduce blocking artifacts. However, both methods generate distinct side effects, such as PSNR degradation or poor de-blocking results, during the de-blocking process. The main objective of our proposed model is to achieve better visual quality and maintain satisfactory coding efficiency simultaneously by integrating the advantages of CGI and OBMC. The introduction of the dual mode selection between CGI and OBMC provides a more flexible mechanism to adjust our objective function and thereby achieves higher objective and subjective coding gains. Experimental results show that our proposed model achieves improved coding efficiency in terms of both PSNR and visual quality.

A critical component of spline smoothing is the choice of knots, especially for curves with varying shapes and frequencies in its domain. We consider a two-stage knot selection scheme for adaptively fitting splines to data subject to noise. A potential set of knots is chosen based on information from certain wavelet decompositions with the intention of placing more points where the curve shows rapid changes. The final knot selection is then made based on statistical model selection ideas. We show that the proposed method is well suited for a variety of smoothing and noise filtering needs.