总变化(TV)正则化已经提高了用于图像处理任务的各种变分模型。我们提出了与电视正则化的早期文献中的倒扩散过程与电视正常化相结合,并表明所得到的增强电视最小化模型对于降低对比度的损失特别有效,这通常由使用电视正常化的模型遇到。我们从嘈杂的额相测量中建立了增强电视模型的稳定重建保证;考虑非自适应线性测量和可变密度采样的傅里叶测量。特别地,在一些较弱的受限制的等距特性条件下,增强的电视最小化模型被示出为比各种基于电视的模型具有更严格的重建误差界限,用于噪声水平很大并且测量量有限。增强电视模型的优点也通过初步实验进行了数值验证,通过一些合成,自然和医学图像的重建。
translated by 谷歌翻译
高维偏微分方程(PDE)是一种流行的数学建模工具,其应用从财务到计算化学不等。但是,用于解决这些PDE的标准数值技术通常受维度的诅咒影响。在这项工作中,我们应对这一挑战,同时着重于在具有周期性边界条件的高维域上定义的固定扩散方程。受到高维度稀疏功能近似进展的启发,我们提出了一种称为压缩傅立叶搭配的新方法。结合了压缩感应和光谱搭配的想法,我们的方法取代了结构化置式网格用蒙特卡洛采样的使用,并采用了稀疏的恢复技术,例如正交匹配的追踪和$ \ ell^1 $最小化,以近似PDE的傅立叶系数解决方案。我们进行了严格的理论分析,表明所提出的方法的近似误差与最佳$ s $ term近似(相对于傅立叶基础)与解决方案相当。我们的分析使用了最近引入的随机采样框架,我们的分析表明,在足够条件下,根据扩散系数的规律性,压缩傅立叶搭配方法相对于搭配点的数量减轻了维数的诅咒。我们还提出了数值实验,以说明稀疏和可压缩溶液近似方法的准确性和稳定性。
translated by 谷歌翻译
This paper considers the model problem of reconstructing an object from incomplete frequency samples. Consider a discrete-time signal f ∈ C N and a randomly chosen set of frequencies Ω of mean size τ N . Is it possible to reconstruct f from the partial knowledge of its Fourier coefficients on the set Ω?A typical result of this paper is as follows: for each M > 0, suppose that f obeysthen with probability at least 1 − O(N −M ), f can be reconstructed exactly as the solution to the ℓ 1 minimization problem min g N −1 t=0 |g(t)|, s.t. ĝ(ω) = f (ω) for all ω ∈ Ω.In short, exact recovery may be obtained by solving a convex optimization problem.We give numerical values for α which depends on the desired probability of success; except for the logarithmic factor, the condition on the size of the support is sharp.The methodology extends to a variety of other setups and higher dimensions. For example, we show how one can reconstruct a piecewise constant (one or two-dimensional) object from incomplete frequency samples-provided that the number of jumps (discontinuities) obeys the condition above-by minimizing other convex functionals such as the total-variation of f .
translated by 谷歌翻译
稀疏数据的恢复是机器学习和信号处理中许多应用的核心。虽然可以使用$ \ ell_1 $ -regularization在套索估算器中使用此类问题,但在基础上,通常需要专用算法来解决大型实例的相应高维非平滑优化。迭代地重新重复的最小二乘(IRLS)是一种广泛使用的算法,其出于其优异的数值性能。然而,虽然现有理论能够保证该算法的收敛到最小化器,但它不提供全局收敛速度。在本文中,我们证明了IRLS的变型以全局线性速率收敛到稀疏解决方案,即,如果测量结果满足通常的空空间属性假设,则立即发生线性误差。我们通过数值实验支持我们的理论,表明我们的线性速率捕获了正确的维度依赖性。我们预计我们的理论调查结果将导致IRLS算法的许多其他用例的新见解,例如在低级矩阵恢复中。
translated by 谷歌翻译
随着对图像重建任务的深度神经网络(DNN)的兴趣,其可靠性已受到质疑(Antun等,2020; Gottschling等,2020)。然而,最近的工作表明,与总变化(TV)最小化相比,它们与对抗性噪声相似,以$ \ ell^2 $ - 重构误差(Genzel等,2022)。我们考虑使用$ \ ell^\ infty $ -norm的不同鲁棒性概念,并认为本地化的重建工件比$ \ ell^2 $ -Error更相关。我们创造了对不足采样的MRI测量值的对抗性扰动,这些测量值在电视调查重建中诱导严重的局部伪影。相同的攻击方法对基于DNN的重建不如有效。最后,我们表明,这种现象是可以保证精确恢复的重建方法固有的,就像用$ \ ell^1 $或TV-最小化的压缩传感重建一样。
translated by 谷歌翻译
本文涉及使用多项式的有限样品的平滑,高维函数的近似。这项任务是计算科学和工程中许多应用的核心 - 尤其是由参数建模和不确定性量化引起的。通常在此类应用中使用蒙特卡洛(MC)采样,以免屈服于维度的诅咒。但是,众所周知,这种策略在理论上是最佳的。尺寸$ n $有许多多项式空间,样品复杂度尺度划分为$ n $。这种有据可查的现象导致了一致的努力,以设计改进的,实际上是近乎最佳的策略,其样本复杂性是线性的,甚至线性地缩小了$ n $。自相矛盾的是,在这项工作中,我们表明MC实际上是高维度中的一个非常好的策略。我们首先通过几个数值示例记录了这种现象。接下来,我们提出一个理论分析,该分析能够解决这种悖论,以实现无限多变量的全体形态功能。我们表明,基于$ M $ MC样本的最小二乘方案,其错误衰减为$ m/\ log(m)$,其速率与最佳$ n $ term的速率相同多项式近似。该结果是非构造性的,因为它假定了进行近似的合适多项式空间的知识。接下来,我们提出了一个基于压缩感应的方案,该方案达到了相同的速率,除了较大的聚类因子。该方案是实用的,并且在数值上,它的性能和比知名的自适应最小二乘方案的性能和更好。总体而言,我们的发现表明,当尺寸足够高时,MC采样非常适合平滑功能近似。因此,改进的采样策略的好处通常仅限于较低维度的设置。
translated by 谷歌翻译
我们研究了趋势过滤的多元版本,称为Kronecker趋势过滤或KTF,因为设计点以$ D $维度形成格子。 KTF是单变量趋势过滤的自然延伸(Steidl等,2006; Kim等人,2009; Tibshirani,2014),并通过最大限度地减少惩罚最小二乘问题,其罚款术语总和绝对(高阶)沿每个坐标方向估计参数的差异。相应的惩罚运算符可以编写单次趋势过滤惩罚运营商的Kronecker产品,因此名称Kronecker趋势过滤。等效,可以在$ \ ell_1 $ -penalized基础回归问题上查看KTF,其中基本功能是下降阶段函数的张量产品,是一个分段多项式(离散样条)基础,基于单变量趋势过滤。本文是Sadhanala等人的统一和延伸结果。 (2016,2017)。我们开发了一套完整的理论结果,描述了$ k \ grone 0 $和$ d \ geq 1 $的$ k ^ {\ mathrm {th}} $ over kronecker趋势过滤的行为。这揭示了许多有趣的现象,包括KTF在估计异构平滑的功能时KTF的优势,并且在$ d = 2(k + 1)$的相位过渡,一个边界过去(在高维对 - 光滑侧)线性泡沫不能完全保持一致。我们还利用Tibshirani(2020)的离散花键来利用最近的结果,特别是离散的花键插值结果,使我们能够将KTF估计扩展到恒定时间内的任何偏离晶格位置(与晶格数量的大小无关)。
translated by 谷歌翻译
近年来,在诸如denoing,压缩感应,介入和超分辨率等反问题中使用深度学习方法的使用取得了重大进展。尽管这种作品主要是由实践算法和实验驱动的,但它也引起了各种有趣的理论问题。在本文中,我们调查了这一作品中一些突出的理论发展,尤其是生成先验,未经训练的神经网络先验和展开算法。除了总结这些主题中的现有结果外,我们还强调了一些持续的挑战和开放问题。
translated by 谷歌翻译
新磁共振(MR)成像方式可以量化血流动力学,但需要长时间的采集时间,妨碍其广泛用于早期诊断心血管疾病。为了减少采集​​时间,常规使用来自未采样测量的重建方法,使得利用旨在提高图像可压缩性的表示。重建的解剖和血液动力学图像可能存在视觉伪影。尽管这些工件中的一些基本上是重建错误,因此欠采样的后果,其他人可能是由于测量噪声或采样频率的随机选择。另有说明,重建的图像变为随机变量,并且其偏差和其协方差都可以导致视觉伪影;后者会导致可能误解的空间相关性以用于视觉信息。虽然前者的性质已经在文献中已经研究过,但后者尚未得到关注。在这项研究中,我们研究了从重建过程产生的随机扰动的理论特性,并对模拟和主动脉瘤进行了许多数值实验。我们的结果表明,当基于$ \ ell_1 $ -norm最小化的高斯欠采样模式与恢复算法组合时,相关长度保持限制为2到三个像素。然而,对于其他欠采样模式,相关长度可以显着增加,较高的欠采样因子(即8倍或16倍压缩)和不同的重建方法。
translated by 谷歌翻译
我们提出了一个基于一般学习的框架,用于解决非平滑和非凸图像重建问题。我们将正则函数建模为$ l_ {2,1} $ norm的组成,并将平滑但非convex功能映射参数化为深卷积神经网络。我们通过利用Nesterov的平滑技术和残留学习的概念来开发一种可证明的趋同的下降型算法来解决非平滑非概念最小化问题,并学习网络参数,以使算法的输出与培训数据中的参考匹配。我们的方法用途广泛,因为人们可以将各种现代网络结构用于正规化,而所得网络继承了算法的保证收敛性。我们还表明,所提出的网络是参数有效的,其性能与实践中各种图像重建问题中的最新方法相比有利。
translated by 谷歌翻译
Discriminative features extracted from the sparse coding model have been shown to perform well for classification. Recent deep learning architectures have further improved reconstruction in inverse problems by considering new dense priors learned from data. We propose a novel dense and sparse coding model that integrates both representation capability and discriminative features. The model studies the problem of recovering a dense vector $\mathbf{x}$ and a sparse vector $\mathbf{u}$ given measurements of the form $\mathbf{y} = \mathbf{A}\mathbf{x}+\mathbf{B}\mathbf{u}$. Our first analysis proposes a geometric condition based on the minimal angle between spanning subspaces corresponding to the matrices $\mathbf{A}$ and $\mathbf{B}$ that guarantees unique solution to the model. The second analysis shows that, under mild assumptions, a convex program recovers the dense and sparse components. We validate the effectiveness of the model on simulated data and propose a dense and sparse autoencoder (DenSaE) tailored to learning the dictionaries from the dense and sparse model. We demonstrate that (i) DenSaE denoises natural images better than architectures derived from the sparse coding model ($\mathbf{B}\mathbf{u}$), (ii) in the presence of noise, training the biases in the latter amounts to implicitly learning the $\mathbf{A}\mathbf{x} + \mathbf{B}\mathbf{u}$ model, (iii) $\mathbf{A}$ and $\mathbf{B}$ capture low- and high-frequency contents, respectively, and (iv) compared to the sparse coding model, DenSaE offers a balance between discriminative power and representation.
translated by 谷歌翻译
自Venkatakrishnan等人的开创性工作以来。 2013年,即插即用(PNP)方法在贝叶斯成像中变得普遍存在。这些方法通过将显式似然函数与预定由图像去噪算法隐式定义的明确定义,导出用于成像中的逆问题的最小均方误差(MMSE)或最大后验误差(MAP)估计器。文献中提出的PNP算法主要不同于他们用于优化或采样的迭代方案。在优化方案的情况下,一些最近的作品能够保证收敛到一个定点,尽管不一定是地图估计。在采样方案的情况下,据我们所知,没有已知的收敛证明。关于潜在的贝叶斯模型和估算器是否具有明确定义,良好的良好,并且具有支持这些数值方案所需的基本规律性属性,还存在重要的开放性问题。为了解决这些限制,本文开发了用于对PNP前锋进行贝叶斯推断的理论,方法和可忽略的会聚算法。我们介绍了两个算法:1)PNP-ULA(未调整的Langevin算法),用于蒙特卡罗采样和MMSE推断; 2)PNP-SGD(随机梯度下降)用于MAP推理。利用Markov链的定量融合的最新结果,我们为这两种算法建立了详细的收敛保证,在现实假设下,在去噪运营商使用的现实假设下,特别注意基于深神经网络的遣散者。我们还表明这些算法大致瞄准了良好的决策理论上最佳的贝叶斯模型。所提出的算法在几种规范问题上证明了诸如图像去纹,染色和去噪,其中它们用于点估计以及不确定的可视化和量化。
translated by 谷歌翻译
We consider the nonlinear inverse problem of learning a transition operator $\mathbf{A}$ from partial observations at different times, in particular from sparse observations of entries of its powers $\mathbf{A},\mathbf{A}^2,\cdots,\mathbf{A}^{T}$. This Spatio-Temporal Transition Operator Recovery problem is motivated by the recent interest in learning time-varying graph signals that are driven by graph operators depending on the underlying graph topology. We address the nonlinearity of the problem by embedding it into a higher-dimensional space of suitable block-Hankel matrices, where it becomes a low-rank matrix completion problem, even if $\mathbf{A}$ is of full rank. For both a uniform and an adaptive random space-time sampling model, we quantify the recoverability of the transition operator via suitable measures of incoherence of these block-Hankel embedding matrices. For graph transition operators these measures of incoherence depend on the interplay between the dynamics and the graph topology. We develop a suitable non-convex iterative reweighted least squares (IRLS) algorithm, establish its quadratic local convergence, and show that, in optimal scenarios, no more than $\mathcal{O}(rn \log(nT))$ space-time samples are sufficient to ensure accurate recovery of a rank-$r$ operator $\mathbf{A}$ of size $n \times n$. This establishes that spatial samples can be substituted by a comparable number of space-time samples. We provide an efficient implementation of the proposed IRLS algorithm with space complexity of order $O(r n T)$ and per-iteration time complexity linear in $n$. Numerical experiments for transition operators based on several graph models confirm that the theoretical findings accurately track empirical phase transitions, and illustrate the applicability and scalability of the proposed algorithm.
translated by 谷歌翻译
我们为特殊神经网络架构,称为运营商复发性神经网络的理论分析,用于近似非线性函数,其输入是线性运算符。这些功能通常在解决方案算法中出现用于逆边值问题的问题。传统的神经网络将输入数据视为向量,因此它们没有有效地捕获与对应于这种逆问题中的数据的线性运算符相关联的乘法结构。因此,我们介绍一个类似标准的神经网络架构的新系列,但是输入数据在向量上乘法作用。由较小的算子出现在边界控制中的紧凑型操作员和波动方程的反边值问题分析,我们在网络中的选择权重矩阵中促进结构和稀疏性。在描述此架构后,我们研究其表示属性以及其近似属性。我们还表明,可以引入明确的正则化,其可以从所述逆问题的数学分析导出,并导致概括属性上的某些保证。我们观察到重量矩阵的稀疏性改善了概括估计。最后,我们讨论如何将运营商复发网络视为深度学习模拟,以确定诸如用于从边界测量的声波方程中重建所未知的WAVESTED的边界控制的算法算法。
translated by 谷歌翻译
本文首先提出了一种凸双翼优化范例,可以在现实世界场景中制定和优化流行的学习和视觉问题。与传统方法不同,直接基于给定的问题制定设计其迭代方案,我们将任务导向的能量引入我们的潜在约束,这集成了更丰富的任务信息。通过明确地重新表征可行性,我们建立了一种高效且灵活的算法框架,可以使用缩小解决方案空间和强大的辅助(基于任务的域知识和数据分布)来解决凸模型。理论上,我们提出了基于潜在可行性重新表征的数值策略的收敛分析。我们还在计算误差扰动下分析了理论会聚的稳定性。进行了广泛的数值实验,以验证我们的理论调查结果,并评估我们对不同应用方法的实际表现。
translated by 谷歌翻译
在Bora等。 (2017年),在测量矩阵为高斯,信号结构是生成神经网络(GNN)的范围的设置中开发了一个数学框架,用于压缩传感保证。此后,当测量矩阵和/或网络权重遵循Subgaussian分布时,对GNNS进行压缩感测的问题进行了广泛的分析。我们超越了高斯的假设,以通过在单一基质的随机行中均匀地采样(包括作为特殊情况下的亚采样傅立叶测量值)来得出的测量矩阵。具体而言,我们证明了使用亚次采样的二型限制感测的第一个已知的限制等轴测保证,并提供了几乎有序的样品复杂性的恢复边界,解决了Scarlett等人的开放问题。 (2022,第10页)。恢复功效的特征是连贯性,这是一个新参数,该参数测量了网络范围与测量矩阵之间的相互作用。我们的方法依赖于子空间计数论点和思想的核心概率。此外,我们提出了一种正规化策略,以使GNN与测量运算符具有有利的连贯性。我们提供令人信服的数值模拟来支持这种正规训练策略:我们的策略产生低相干网络,需要更少的信号回收测量。这与我们的理论结果一起支持连贯性作为自然量,用于表征与亚次采样的生成压缩感测。
translated by 谷歌翻译
This paper is about a curious phenomenon. Suppose we have a data matrix, which is the superposition of a low-rank component and a sparse component. Can we recover each component individually? We prove that under some suitable assumptions, it is possible to recover both the low-rank and the sparse components exactly by solving a very convenient convex program called Principal Component Pursuit; among all feasible decompositions, simply minimize a weighted combination of the nuclear norm and of the 1 norm. This suggests the possibility of a principled approach to robust principal component analysis since our methodology and results assert that one can recover the principal components of a data matrix even though a positive fraction of its entries are arbitrarily corrupted. This extends to the situation where a fraction of the entries are missing as well. We discuss an algorithm for solving this optimization problem, and present applications in the area of video surveillance, where our methodology allows for the detection of objects in a cluttered background, and in the area of face recognition, where it offers a principled way of removing shadows and specularities in images of faces.
translated by 谷歌翻译
通过结合使用卷积神经网(CNN)指定的物理测量模型和学习的图像验证者,对基于模型的架构(DMBA)的兴趣越来越大。例如,用于系统设计DMBA的著名框架包括插件培训(PNP),深度展开(DU)和深度平衡模型(DEQ)。尽管已广泛研究了DMBA的经验性能和理论特性,但当确切地知道所需的图像之前,该地区的现有工作主要集中在其性能上。这项工作通过在不匹配的CNN先验下向DMBA提供新的理论和数值见解来解决先前工作的差距。当训练和测试数据之间存在分布变化时,自然会出现不匹配的先验,例如,由于测试图像来自与用于训练CNN先验的图像不同的分布。当CNN事先用于推理是一些所需的统计估计器(MAP或MMSE)的近似值时,它们也会出现。我们的理论分析在一组明确指定的假设下,由于不匹配的CNN先验,在解决方案上提供了明显的误差界限。我们的数值结果比较了在现实分布变化和近似统计估计器下DMBA的经验性能。
translated by 谷歌翻译
We consider the problem of estimating a multivariate function $f_0$ of bounded variation (BV), from noisy observations $y_i = f_0(x_i) + z_i$ made at random design points $x_i \in \mathbb{R}^d$, $i=1,\ldots,n$. We study an estimator that forms the Voronoi diagram of the design points, and then solves an optimization problem that regularizes according to a certain discrete notion of total variation (TV): the sum of weighted absolute differences of parameters $\theta_i,\theta_j$ (which estimate the function values $f_0(x_i),f_0(x_j)$) at all neighboring cells $i,j$ in the Voronoi diagram. This is seen to be equivalent to a variational optimization problem that regularizes according to the usual continuum (measure-theoretic) notion of TV, once we restrict the domain to functions that are piecewise constant over the Voronoi diagram. The regression estimator under consideration hence performs (shrunken) local averaging over adaptively formed unions of Voronoi cells, and we refer to it as the Voronoigram, following the ideas in Koenker (2005), and drawing inspiration from Tukey's regressogram (Tukey, 1961). Our contributions in this paper span both the conceptual and theoretical frontiers: we discuss some of the unique properties of the Voronoigram in comparison to TV-regularized estimators that use other graph-based discretizations; we derive the asymptotic limit of the Voronoi TV functional; and we prove that the Voronoigram is minimax rate optimal (up to log factors) for estimating BV functions that are essentially bounded.
translated by 谷歌翻译
我们考虑最小化高维目标函数的问题,该功能可以包括正则化术语,使用(可能的噪声)评估该功能。这种优化也称为无衍生,零阶或黑匣子优化。我们提出了一个新的$ \ textbf {z} $ feroth - $ \ textbf {o} $ rder $ \ textbf {r} $ ptimization方法,称为zoro。当潜在的梯度大致稀疏时,Zoro需要很少的客观函数评估,以获得降低目标函数的新迭代。我们通过自适应,随机梯度估计器实现这一点,然后是不精确的近端梯度方案。在一个新颖的大致稀疏梯度假设和各种不同的凸面设置下,我们显示了zoro的(理论和实证)收敛速率仅对对数依赖于问题尺寸。数值实验表明,Zoro在合成和实际数据集中优于具有相似假设的现有方法。
translated by 谷歌翻译