检索结果-内蒙古大学图书馆

SparseAlign: A Grid-Free Algorithm for Automatic Marker Localization and Deformation Estimation in Cryo-Electron Tomography

引用

IEEE TRANSACTIONS ON COMPUTATIONAL IMAGING 2022年 8卷 651-665页

作者： Ganguly, Poulami Somanya Lucka, Felix Kohr, Holger Franken, Erik Hupkes, Hermen Jan Batenburg, Kees Joost Ctr Wiskunde & Informat Computat Imaging NL-1098 XG Amsterdam Netherlands Leiden Univ Math Inst NL-2311 EZ Leiden Netherlands Ctr Wiskunde & Informat Computat Imaging Grp NL-1098 XG Amsterdam Netherlands Thermo Fisher Sci NL-5644 Eindhoven Netherlands Leiden Univ Math Inst NL-2311 FZ Leiden Netherlands Leiden Univ Leiden Inst Adv Comp Sci NL-2311 EZ Leiden Netherlands

Tilt-series alignment is crucial to obtaining high-resolution reconstructions in cryo-electron tomography. Beam-induced local deformation of the sample is hard to estimate from the low-contrast sample alone, and often requires fiducial gold bead markers. The state-of-the-art approach for deformation estimation uses (semi-)manually labelled marker locations in projection data to fit the parameters of a polynomial deformation model. Manually-labelled marker locations are difficult to obtain when data are noisy or markers overlap in projection data. We propose an alternative mathematical approach for simultaneous marker localization and deformation estimation by extending a grid-free algorithm first proposed in the context of super-resolution single-molecule localization microscopy. Our approach does not require labelled marker locations;instead, we use an image-based loss where we compare the forward projection of markers with the observed data. We equip this marker localization scheme with an additional deformation estimation component and solve for a reduced number of deformation parameters. Using extensive numerical studies on marker-only samples, we show that our approach automatically finds markers and reliably estimates sample deformation without labelled marker data. We further demonstrate the applicability of our approach for a broad range of model mismatch scenarios, including experimental electron tomography data of gold markers on ice.

关键词： Mathematical super-resolution parallel-beam tomography conditional gradient method marker-based alignment

来源：评论

学校读者我要写书评

暂无评论

An away-step Frank-Wolfe algorithm for constrained multiobjective optimization

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2024年第3期88卷 759-781页

作者： Goncalves, Douglas S. Goncalves, Max L. N. Melo, Jefferson G. Univ Fed Santa Catarina Dept Matemat BR-88040900 Florianopolis SC Brazil Univ Fed Goias IME BR-74001970 Goiania Go Brazil

In this paper, we propose and analyze an away-step Frank-Wolfe algorithm designed for solving multiobjective optimization problems over polytopes. We prove that each limit point of the sequence generated by the algorithm is a weak Pareto optimal solution. Furthermore, under additional conditions, we show linear convergence of the whole sequence to a Pareto optimal solution. Numerical examples illustrate a promising performance of the proposed algorithm in problems where the multiobjective Frank-Wolfe convergence rate is only sublinear.

关键词： Frank-Wolfe algorithm conditional gradient method Away-step Linear convergence rate Pareto optimality Constrained multiobjective problem

来源：评论

学校读者我要写书评

暂无评论

UNIVERSAL conditional gradient SLIDING FOR CONVEX OPTIMIZATION

引用

SIAM JOURNAL ON OPTIMIZATION 2023年第4期33卷 2962-2987页

作者： Ouyang, Yuyuan Squires, Trevor Clemson Univ Sch Math & Stat Sci Clemson SC 29631 USA

In this paper, we present a first-order projection-free method, namely, the universal conditional gradient sliding (UCGS) method, for computing epsilon-approximate solutions to convex differentiable optimization problems with bounded domains. For objective functions with Holder continuous gradients under the Euclidean norm we show that UCGS is able to terminate with epsilon-solutions with at most O((M-nu D-X(1+nu) /epsilon)(2/(1+3 nu))) gradient evaluations and O((M-nu D-X(1+nu) /epsilon)(4/(1+3 nu))) linear objective optimizations, where nu is an element of(0, 1] and M-nu > 0 are the exponent and constant of the Holder condition and DX is the diameter of the constraint set. Furthermore, UCGS is able to perform such computations without requiring any specific knowledge of the smoothness information nu and M-nu. In the weakly smooth case when nu is an element of(0, 1), both complexity results improve the current state-of-the-art O((M-nu D-X(1+nu) /epsilon)(1/nu)) results Y. Nesterov, Math. Program., 171 (2018), pp. 311-330, S. Ghadimi, Math. Program., 173 (2019), pp. 431-464 on a first-order projection-free method achieved by the conditional gradient method. Within the class of sliding-type algorithms following from the work of G. Lan and Y. Zhou, SIAM J. Optim., 26 (2016), pp. 1379-1409, Y. Chen, G. Lan, Y. Ouyang, and W. Zhang, Comput. Optim. Appl., 73 (2019), pp. 159-199, to the best of our knowledge, this is the first time a sliding-type algorithm has been able to improve not only the gradient complexity but also the overall complexity for computing an approximate solution. In the smooth case when nu = 1, UCGS matches the state-of-the-art complexity result achieved by the conditional gradient sliding method G. Lan and Y. Zhou, SIAM J. Optim., 26 (2016), pp. 1379-1409, but adds more features allowing for practical implementation.

关键词： convex optimization first-order method conditional gradient method conditional gradient sliding universal gradient method

来源：评论

学校读者我要写书评

暂无评论

STOCHASTIC conditional gradient plus plus : (NON)CONVEX MINIMIZATION AND CONTINUOUS SUBMODULAR MAXIMIZATION

引用

SIAM JOURNAL ON OPTIMIZATION 2020年第4期30卷 3315-3344页

作者： Hassani, Hamed Karbasi, Amin Mokhtari, Aryan Shen, Zebang Univ Penn Dept Elect & Syst Engn Philadelphia PA 19104 USA Yale Univ Dept Elect Engn & Comp Sci New Haven CT 06511 USA Univ Texas Austin Dept Elect & Comp Engn Austin TX 78712 USA

In this paper, we consider the general nonoblivious stochastic optimization where the underlying stochasticity may change during the optimization procedure and depends on the point at which the function is evaluated. We develop Stochastic Frank-Wolfe++ (SFW++), an efficient variant of the conditional gradient method for minimizing a smooth nonconvex function subject to a convex body constraint. We show that SFW++ converges to an epsilon-first order stationary point by using O(1/epsilon(3)) stochastic gradients. Once further structures are present, SFW++'s theoretical guarantees, in terms of the convergence rate and quality of its solution, improve. In particular, for minimizing a convex function, SFW++ achieves an epsilon-approximate optimum while using O(1/epsilon(2)) stochastic gradients. It is known that this rate is optimal in terms of stochastic gradient evaluations. Similarly, for maximizing a monotone continuous DR-submodular function, a slightly different form of SFW++, called Stochastic Continuous Greedy++ (SCG++), achieves a tight [(1 - 1/e)OPT - epsilon] solution while using O(1/epsilon(2)) stochastic gradients. Through an information theoretic argument, we also prove that SCG++'s convergence rate is optimal. Finally, for maximizing a nonmonotone continuous DR-submodular function, we can achieve a [(1/e)OPT - epsilon] solution by using O(1/epsilon(2)) stochastic gradients. We should highlight that our results and our novel variance reduction technique trivially extend to the standard and easier oblivious stochastic optimization settings for (non)convex and continuous submodular settings.

关键词： nonconvex minimization submodular maximization stochastic optimization conditional gradient method first order method variance reduction

来源：评论

学校读者我要写书评

暂无评论

conditional gradient SLIDING FOR CONVEX OPTIMIZATION

引用

SIAM JOURNAL ON OPTIMIZATION 2016年第2期26卷 1379-1409页

作者： Lan, Guanghui Zhou, Yi Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA

In this paper, we present a new conditional gradient type method for convex optimization by calling a linear optimization (LO) oracle to minimize a series of linear functions over the feasible set. Different from the classic conditional gradient method, the conditional gradient sliding (CGS) algorithm developed herein can skip the computation of gradients from time to time and, as a result, can achieve the optimal complexity bounds in terms of not only the number of calls to the LO oracle but also the number of gradient evaluations. More specifically, we show that the CGS method requires O (1/root epsilon) and O(log(1/epsilon)) gradient evaluations, respectively, for solving smooth and strongly convex problems, while still maintaining the optimal O(1/epsilon) bound on the number of calls to the LO oracle. We also develop variants of the CGS method which can achieve the optimal complexity bounds for solving stochastic optimization problems and an important class of saddle point optimization problems. To the best of our knowledge, this is the first time that these types of projection-free optimal first-order methods have been developed in the literature. Some preliminary numerical results have also been provided to demonstrate the advantages of the CGS method.

关键词： convex programming complexity conditional gradient method Frank-Wolfe method Nesterov's method

来源：评论

学校读者我要写书评

暂无评论

A Momentum-Guided Frank-Wolfe Algorithm

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2021年 69卷 3597-3611页

作者： Li, Bingcong Coutino, Mario B. Giannakis, Georgios Leus, Geert Univ Minnesota Dept Elect & Comp Engn Minneapolis MN 55455 USA Univ Minnesota Digital Technol Ctr Minneapolis MN 55455 USA Delft Univ Technol EEMCS Dept Microelect Circuits & Syst Grp NL-2628 CD Delft Netherlands TNO Radar Technol The Hague Netherlands

With the well-documented popularity of Frank Wolfe (FW) algorithms in machine learning tasks, the present paper establishes links between FW subproblems and the notion of momentum emerging in accelerated gradient methods (AGMs). On the one hand, these links reveal why momentum is unlikely to be effective for FW-type algorithms on general problems. On the other hand, it is established that momentum accelerates FW on a class of signal processing and machine learning applications. Specifically, it is proved that a momentum variant of FW, here termed accelerated Frank Wolfe (AFW), converges with a faster rate O(1/k(2)) on such a family of problems, despite the same O(1/k) rate of FW on general cases. Distinct from existing fast convergent FW variants, the faster rates here rely on parameter-free step sizes. Numerical experiments on benchmarked machine learning tasks corroborate the theoretical findings.

关键词： Frank Wolfe method conditional gradient method momentum accelerated method smooth convex optimization

来源：评论

学校读者我要写书评

暂无评论

ON THE CONVEXITY OF INTEGRALS OF MULTIVALUED MAPPINGS - APPLICATIONS IN CONTROL-THEORY

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1987年第3期54卷 541-563页

作者： VELIOV, VM Institute of Mathematics Bulgarian Academy of Sciences Sofia Bulgaria

Using the notion of the local convexity index, we characterize in a quantitative way the local convexity of a set in then-dimensional Euclidean space, defined by an integral of a multivalued mapping. We estimate the rate of convergence of the conditional gradient method for solving an abstract optimization problem by means of the convexity index of the constraining set at the solution point. These results are applied to the qualitative analysis of the solutions of time-optimal and Mayer problems for linear control systems, as well as for estimating the convergence rate of algorithms solving these problems.

关键词： attainable set conditional gradient method constrained optimization convexity Integrals of multivalued mappings linear optimal control

来源：评论

学校读者我要写书评

暂无评论

Extragradient method with feasible inexact projection to variational inequality problem

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2024年第2期89卷 459-484页

作者： Millan, R. Diaz Ferreira, O. P. Ugon, J. Deakin Univ Sch Informat Technol Geelong Australia Univ Fed Goias IME Goiania Brazil

The variational inequality problem in finite-dimensional Euclidean space is addressed in this paper, and two inexact variants of the extragradient method are proposed to solve it. Instead of computing exact projections on the constraint set, as in previous versions extragradient method, the proposed methods compute feasible inexact projections on the constraint set using a relative error criterion. The first version of the proposed method provided is a counterpart to the classic form of the extragradient method with constant steps. In order to establish its convergence we need to assume that the operator is pseudo-monotone and Lipschitz continuous, as in the standard approach. For the second version, instead of a fixed step size, the method presented finds a suitable step size in each iteration by performing a line search. Like the classical extragradient method, the proposed method does just two projections into the feasible set in each iteration. A full convergence analysis is provided, with no Lipschitz continuity assumption of the operator defining the variational inequality problem.

关键词： Variational inequality problem Extragradient method Frank-Wolfe algorithm conditional gradient method Feasible inexact projection

来源：评论

学校读者我要写书评

暂无评论

Improved complexities of conditional gradient-type methods with applications to robust matrix recovery problems

引用

MATHEMATICAL PROGRAMMING 2021年第1-2期186卷 185-208页

作者： Garber, Dan Kaplan, Atara Sabach, Shoham Technion Fac Ind Engn & Management IL-32000 Haifa Israel Technion Dept Math IL-32000 Haifa Israel

Motivated by robust matrix recovery problems such as Robust Principal Component Analysis, we consider a general optimization problem of minimizing a smooth and strongly convex loss function applied to the sum of two blocks of variables, where each block of variables is constrained or regularized individually. We study a conditional gradient-Type method which is able to leverage the special structure of the problem to obtain faster convergence rates than those attainable via standard methods, under a variety of assumptions. In particular, our method is appealing for matrix problems in which one of the blocks corresponds to a low-rank matrix since it avoids prohibitive full-rank singular value decompositions required by most standard methods. While our initial motivation comes from problems which originated in statistics, our analysis does not impose any statistical assumptions on the data.

关键词： conditional gradient method Frank-Wolfe algorithm Convex optimization Robust PCA Low-rank matrix recovery Low-rank optimization Semidefinite programming Nuclear norm minimization

来源：评论

学校读者我要写书评

暂无评论

Complexity bounds for primal-dual methods minimizing the model of objective function

引用

MATHEMATICAL PROGRAMMING 2018年第1-2期171卷 311-330页

作者： Nesterov, Yu. Catholic Univ Louvain UCL CORE 34 Voie Roman Pays B-1348 Louvain La Neuve Belgium

We provide Frank-Wolfe (equivalent to conditional gradients) method with a convergence analysis allowing to approach a primal-dual solution of convex optimization problem with composite objective function. Additional properties of complementary part of the objective (strong convexity) significantly accelerate the scheme. We also justify a new variant of this method, which can be seen as a trust-region scheme applying to the linear model of objective function. For this variant, we prove also the rate of convergence for the total variation of linear model of composite objective over the feasible set. Our analysis works also for quadratic model, allowing to justify the global rate of convergence for a new second-order method as applied to a composite objective function. To the best of our knowledge, this is the first trust-region scheme supported by the worst-case complexity analysis both for the functional gap and for the variation of local quadratic model over the feasible set.

关键词： Convex optimization Complexity bounds Linear optimization oracle conditional gradient method Trust-region method

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：