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

62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Ding, Jingqiu D'Orsi, Tommaso Nasser, Rajai Steurer, David Swiss Fed Inst Technol Comp Sci Dept Zurich Switzerland

ISBN: (纸本)9781665420556

We develop an efficient algorithm for weak recovery in a robust version of the stochastic block model. The algorithm matches the statistical guarantees of the best known algorithms for the vanilla version of the stochastic block model. In this sense, our results show that there is no price of robustness in the stochastic block model. Our work is heavily inspired by recent work of Banks, Mohanty, and Raghavendra (SODA 2021) that provided an efficient algorithm for the corresponding distinguishing problem. Our algorithm and its analysis significantly depart from previous ones for robust recovery. A key challenge is the peculiar optimization landscape underlying our algorithm: The planted partition may be far from optimal in the sense that completely unrelated solutions could achieve the same objective value. This phenomenon is related to the push-out effect at the BBP phase transition for PCA. To the best of our knowledge, our algorithm is the first to achieve robust recovery in the presense of such a push-out effect in a non-asymptotic setting. Our algorithm is an instantiation of a framework based on convex optimization (related to but distinct from sum-of-squares), which may be useful for other robust matrix estimation problems. A by-product of our analysis is a general technique that boosts the probability of success (over the randomness of the input) of an arbitrary robust weak-recovery algorithm from constant (or slowly vanishing) probability to exponentially high probability.

关键词： stochastic block model robust algorithms robust recovery convex optimization semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

robust phase retrieval via median-truncated smoothed amplitude flow

引用

INVERSE PROBLEMS IN SCIENCE AND ENGINEERING 2021年第13期29卷 3024-3040页

作者： Luo, Qi Lin, Shijian Wang, Hongxia Natl Univ Def Technol Dept Math Changsha 410073 Hunan Peoples R China Natl Univ Def Technol Dept Comp Sci Changsha Peoples R China

Phase retrieval (PR) is an inverse problem about recovering a signal from phaseless linear measurements, which arises in various fields. In practical scenarios, partial measurements can be inevitably corrupted by outliers that can take arbitrary values. To handle this, we propose the median-SAF method which is the smoothed amplitude flow (SAF) method equipped with the median truncation strategy. We find that median-SAF has some inherent advantages in suppressing outliers. Theoretical analysis ensures that median-SAF converges linearly to the original signal via the gradient algorithm from an delicate initial estimate with high probability. Substantial numerical tests empirically illustrate that the proposed method is superior to other state-of-the-art methods in terms of the recovery rate and the performance on suppressing outliers.

关键词： Statistical signal processing nonconvex optimization phase retrieval gradient descent robust algorithms

来源：评论

学校读者我要写书评

暂无评论

robust ADAPTIVE POWER ALLOCATION FOR THE DOWNLINK OF MULTIPLE-ANTENNA SYSTEMS 21

ROBUST ADAPTIVE POWER ALLOCATION FOR THE DOWNLINK OF MULTIPL...

引用

IEEE Statistical Signal Processing Workshop (SSP)

作者： Flores, Andre R. de Lamare, Rodrigo C. Pontifical Catholic Univ Rio de Janeiro Ctr Telecommun Studies CETUC Rio De Janeiro Brazil

ISBN: (纸本)9781728157672

Multiple-input multiple-output (MIMO) systems greatly increase the overall throughput of wireless systems since they are capable of transmitting multiple streams employing the same time-frequency resources. However, this gain requires an appropriate precoder design and a power allocation technique. In general, precoders and power allocation schemes are designed assuming perfect channel estate information (CSI). Nonetheless, this is an optimistic assumption since real systems only possess partial or imperfect CSI at the transmitter (CSIT). The imperfect CSIT originates residual inter-user interference, which is detrimental for wireless systems. In this paper, two adaptive power allocation algorithms are proposed, which are more robust against CSIT imperfections than conventional techniques. Both techniques employ the mean square error as the objective function. Simulation results show that the proposed techniques obtain a higher performance in terms of sum-rate than conventional approaches.

关键词： Multiuser MIMO systems power allocation adaptive techniques robust algorithms

来源：评论

学校读者我要写书评

暂无评论

Online computation with untrusted advice

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2024年 144卷

作者： Angelopoulos, Spyros Durr, Christoph Jin, Shendan Kamali, Shahin Renault, Marc Sorbonne Univ CNRS Lab Informat Paris 6 LIP6 Paris France Univ Chile CNRS CMM Santiago Chile York Univ Dept Elect Engn & Comp Sci Toronto ON Canada Univ Wisconsin Madison Comp Sci Dept Madison WI USA Sorbonne Univ CNRS LIP6 Paris France

We study a generalization of the advice complexity model of online computation in which the advice is provided by an untrusted source. Our objective is to quantify the impact of untrusted advice so as to design and analyze online algorithms that are robust if the advice is adversarial, and efficient is the advice is foolproof. We focus on four well-studied online problems, namely ski rental, online bidding, bin packing and list update. For ski rental and online bidding, we show how to obtain algorithms that are Pareto-optimal with respect to the competitive ratios achieved, whereas for bin packing and list update, we give online algorithms with worst-case tradeoffs in their competitiveness, depending on whether the advice is trusted or adversarial. More importantly, we demonstrate how to prove lower bounds, within this model, on the tradeoff between the number of advice bits and the competitiveness of any online algorithm. (c) 2024 Elsevier Inc. All rights reserved.

关键词： Online computation Competitive analysis Advice complexity robust algorithms Untrusted advice

来源：评论

学校读者我要写书评

暂无评论

Augmented Lagrangian preconditioners for the Oseen-Frank model of nematic and cholesteric liquid crystals

引用

BIT NUMERICAL MATHEMATICS 2021年第2期61卷 607-644页

作者： Xia, Jingmin Farrell, Patrick E. Wechsung, Florian Univ Oxford Math Inst Oxford England NYU Courant Inst Math Sci New York NY USA

We propose a robust and efficient augmented Lagrangian-type preconditioner for solving linearizations of the Oseen-Frank model arising in nematic and cholesteric liquid crystals. By applying the augmented Lagrangian method, the Schur complement of the director block can be better approximated by the weighted mass matrix of the Lagrange multiplier, at the cost of making the augmented director block harder to solve. In order to solve the augmented director block, we develop a robust multigrid algorithm which includes an additive Schwarz relaxation that captures a pointwise version of the kernel of the semi-definite term. Furthermore, we prove that the augmented Lagrangian term improves the discrete enforcement of the unit-length constraint. Numerical experiments verify the efficiency of the algorithm and its robustness with respect to problem-related parameters (Frank constants and cholesteric pitch) and the mesh size.

关键词： Augmented Lagrangian Oseen– Frank Cholesteric liquid crystal Preconditioning robust algorithms Multigrid

来源：评论

学校读者我要写书评

暂无评论

Information Elicitation from Rowdy Crowds 21

Information Elicitation from Rowdy Crowds

引用

30th World Wide Web Conference (WWW)

作者： Schoenebeck, Grant Yu, Fang-Yi Zhang, Yichi Univ Michigan Ann Arbor MI 48109 USA Harvard Univ Boston MA 02115 USA

ISBN: (纸本)9781450383127

We initiate the study of information elicitation mechanisms for a crowd containing both self-interested agents, who respond to incentives, and adversarial agents, who may collude to disrupt the system. Our mechanisms work in the peer prediction setting where ground truth need not be accessible to the mechanism or even exist. We provide a meta-mechanism that reduces the design of peer prediction mechanisms to a related robust learning problem. The resulting mechanisms are epsilon-informed truthful, which means truth-telling is the highest paid epsilon-Bayesian Nash equilibrium (up to epsilon-error) and pays strictly more than uninformative equilibria. The value of epsilon depends on the properties of robust learning algorithm, and typically limits to 0 as the number of tasks and agents increase. We show how to use our meta-mechanism to design mechanisms with provable guarantees in two important crowdsourcing settings even when some agents are self-interested and others are adversarial.

关键词： information elicitation crowdscourcing robust algorithms

来源：评论

学校读者我要写书评

暂无评论

robust CUR Decomposition: Theory and Imaging Applications*

引用

SIAM JOURNAL ON IMAGING SCIENCES 2021年第4期14卷 1472-1503页

作者： Cai, HanQin Hamm, Keaton Huang, Longxiu Needell, Deanna Univ Calif Los Angeles Dept Math Los Angeles CA 90095 USA Univ Texas Arlington Dept Math Arlington TX 76019 USA

This paper considers the use of robust principal component analysis (RPCA) in a CUR decomposition framework and applications thereof. Our main algorithms produce a robust version of columnrow factorizations of matrices D = L + S, where L is low-rank and S contains sparse outliers. These methods yield interpretable factorizations at low computational cost and provide new CUR decompositions that are robust to sparse outliers, in contrast to previous methods. We consider two key imaging applications of RPCA: video foreground-background separation and face modeling. This paper examines the qualitative behavior of our robust CUR decompositions on the benchmark videos and face datasets and finds that our method works as well as standard RPCA while being significantly faster. Additionally, we consider hybrid randomized and deterministic sampling methods which produce a compact CUR decomposition of a given matrix and apply this to video sequences to produce canonical frames thereof.

关键词： CUR decomposition RPCA robust CUR low-rank matrix approximation interpolative decom-positions robust algorithms

来源：评论

学校读者我要写书评

暂无评论

Non-convex low-rank matrix recovery with arbitrary outliers via median-truncated gradient descent

引用

INFORMATION AND INFERENCE-A JOURNAL OF THE IMA 2020年第2期9卷 289-325页

作者： Li, Yuanxin Chi, Yuejie Zhang, Huishuai Liang, Yingbin Carnegie Mellon Univ Dept Elect & Comp Engn Pittsburgh PA 15213 USA Microsoft Res Asia Beijing 100080 Peoples R China

Recent work has demonstrated the effectiveness of gradient descent for directly recovering the factors of low-rank matrices from random linear measurements in a globally convergent manner when initialized properly. However, the performance of existing algorithms is highly sensitive in the presence of outliers that may take arbitrary values. In this paper, we propose a truncated gradient descent algorithm to improve the robustness against outliers, where the truncation is performed to rule out the contributions of samples that deviate significantly from the sample median of measurement residuals adaptively in each iteration. We demonstrate that, when initialized in a basin of attraction close to the ground truth, the proposed algorithm converges to the ground truth at a linear rate for the Gaussian measurement model with a near-optimal number of measurements, even when a constant fraction of the measurements are arbitrarily corrupted. In addition, we propose a new truncated spectral method that ensures an initialization in the basin of attraction at slightly higher requirements. We finally provide numerical experiments to validate the superior performance of the proposed approach.

关键词： median-truncated gradient descent low-rank matrix recovery non-convex approach robust algorithms outliers

来源：评论

学校读者我要写书评

暂无评论

Blocked algorithms for robust Solution of Triangular Linear Systems 12th

Blocked Algorithms for Robust Solution of Triangular Linear ...

引用

12th International Conference on Parallel Processing and Applied Mathematics (PPAM)

作者： Mikkelsen, Carl Christian Kjelgaard Karlsson, Lars Umea Univ Dept Comp Sci S-90187 Umea Sweden

ISBN: (纸本)9783319780245;9783319780238

We consider the problem of computing a scaling a such that the solution x of the scaled linear system Tx = ab can be computed without exceeding an overflow threshold Omega. Here T is a non-singular upper triangular matrix and b is a single vector, and Omega is less than the largest representable number. This problem is central to the computation of eigenvectors from Schur forms. We show how to protect individual arithmetic operations against overflow and we present a robust scalar algorithm for the complete problem. Our algorithm is very similar to xLATRS in LAPACK. We explain why it is impractical to parallelize these algorithms. We then derive a robust blocked algorithm which can be executed in parallel using a task- based run- time system such as StarPU. The parallel overhead is increased marginally compared with regular blocked backward substitution.

关键词： Triangular linear systems Overflow Blocked algorithms robust algorithms

来源：评论

学校读者我要写书评

暂无评论

Scheduling When You Do Not Know the Number of Machines

引用

ACM TRANSACTIONS ON algorithms 2020年第1期16卷 9-9页

作者： Stein, Clifford Zhong, Mingxian Columbia Univ 500 West 120th St New York NY 10027 USA CUNY Lehman Coll 250 Bedford Pk Blvd W Bronx NY 10468 USA CUNY Grad Ctr 250 Bedford Pk Blvd W Bronx NY 10468 USA

Often in a scheduling problem, there is uncertainty about the jobs to be processed. The issue of uncertainty regarding the machines has been much less studied. In this article, we study a scheduling environment in which jobs first need to be grouped into some sets before the number of machines is known, and then the sets need to be scheduled on machines without being separated. To evaluate algorithms in such an environment, we introduce the idea of an alpha-robust algorithm, one that is guaranteed to return a schedule on any number m of machines that is within an a factor of the optimal schedule on m machine, where the optimum is not subject to the restriction that the sets cannot be separated. Under such environment, we give a (5/2 + epsilon)-robust algorithm for scheduling on parallel machines to minimize makespan and show a lower bound 4/3. For the special case when the jobs are infinitesimal, we give a 1.233-robust algorithm with an asymptotic lower bound of 1.207. We also study a case of fair allocation, where the objective is to minimize the difference between the maximum and minimum machine load.

关键词： robust algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：