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

greedy algorithms for nonnegativity-constrained simultaneous sparse recovery

SIGNAL PROCESSING 2016年 125卷 274-289页

作者： Kim, Daeun Haldar, Justin P. Univ So Calif Ming Hsieh Dept Elect Engn Signal & Image Proc Inst Los Angeles CA 90089 USA

This work proposes a family of greedy algorithms to jointly reconstruct a set of vectors that are (i) nonnegative and (ii) simultaneously sparse with a shared support set. The proposed algorithms generalize previous approaches that were designed to impose these constraints individually. Similar to previous greedy algorithms for sparse recovery, the proposed algorithms iteratively identify promising support indices. In contrast to previous approaches, the support index selection procedure has been adapted to prioritize indices that are consistent with both the nonnegativity and shared support constraints. Empirical results demonstrate for the first time that the combined use of simultaneous sparsity and nonnegativity constraints can substantially improve recovery performance relative to existing greedy algorithms that impose less signal structure. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Compressed Sensing Simultaneous sparsity Nonnegativity greedy algorithms

来源：评论

学校读者我要写书评

暂无评论

greedy algorithms for diffuse optical tomography reconstruction

引用

OPTICS COMMUNICATIONS 2018年 410卷 164-173页

作者： Dileep, B. P. V. Das, Tapan Dutta, Pranab K. IIT Kharagpur Dept Elect Engn Kharagpur 721302 W Bengal India

Diffuse optical tomography (DOT) is a noninvasive imaging modality that reconstructs the optical parameters of a highly scattering medium. However, the inverse problem of DOT is ill-posed and highly nonlinear due to the zig-zag propagation of photons that diffuses through the cross section of tissue. The conventional DOT imaging methods iteratively compute the solution of forward diffusion equation solver which makes the problem computationally expensive. Also, these methods fail when the geometry is complex. Recently, the theory of compressive sensing (CS) has received considerable attention because of its efficient use in biomedical imaging applications. The objective of this paper is to solve a given DOT inverse problem by using compressive sensing framework and various greedy algorithms such as orthogonal matching pursuit (OMP), compressive sampling matching pursuit (CoSaMP), and stagewise orthogonal matching pursuit (StOMP), regularized orthogonal matching pursuit (ROMP) and simultaneous orthogonal matching pursuit (S-OMP) have been studied to reconstruct the change in the absorption parameter i.e, Delta alpha from the boundary data. Also, the greedy algorithms have been validated experimentally on a paraffin wax rectangular phantom through a well designed experimental set up. We also have studied the conventional DOT methods like least square method and truncated singular value decomposition (TSVD) for comparison. One of the main features of this work is the usage of less number of source-detector pairs, which can facilitate the use of DOT in routine applications of screening. The performance metrics such as mean square error (MSE), normalized mean square error (NMSE), structural similarity index (SSIM), and peak signal to noise ratio (PSNR) have been used to evaluate the performance of the algorithms mentioned in this paper. Extensive simulation results confirm that CS based DOT reconstruction outperforms the conventional DOT imaging methods in terms of compu

关键词： Diffuse optical tomography (DOT) Single measurement vector (SMV) Multiple measurement vectors (MMV) greedy algorithms

来源：评论

学校读者我要写书评

暂无评论

greedy algorithms for the profit-aware social team formation problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第1期44卷 94-118页

作者： Liu, Shengxin Poon, Chung Keung Harbin Inst Technol Shenzhen Sch Comp Sci & Technol Shenzhen Peoples R China Hang Seng Univ Hong Kong Dept Comp Hong Kong Peoples R China

Motivated by applications in online labor markets, we study the problem of forming multiple teams of experts in a social network to accomplish multiple tasks that require different combinations of skills. Our goal is to maximize the total profit of tasks that are completed by these teams subject to the capacity constraints of the experts. We study both the offline and online settings of the problem. For the offline problem, we present a simple and practical algorithm that improves upon previous results in many situations. For the online problem, we design competitive deterministic and randomized online algorithms. These are complemented by some hardness results in both settings.

关键词： Team formation greedy algorithms Social networks Lower bounds

来源：评论

学校读者我要写书评

暂无评论

greedy algorithms in Datalog

引用

THEORY AND PRACTICE OF LOGIC PROGRAMMING 2001年第4期1卷 381-407页

作者： Greco, S Univ Calabria Dipartimento Elettron Informat & Sistemist I-87030 Arcavacata Di Rende Italy Univ Calif Los Angeles Dept Comp Sci Los Angeles CA 90024 USA

In the design of algorithms, the greedy paradigm provides a powerful tool for solving efficiently classical computational problems, within the framework of procedural languages. However, expressing these algorithms within the declarative framework of logic-based languages has proven a difficult research challenge. In this paper, we extend the framework of Datalog-like languages to obtain simple declarative formulations for such problems. and propose effective implementation techniques to ensure computational complexities comparable to those of procedural formulations. These advances are achieved through the use of the choice construct, extended with preference annotations to effect the selection of alternative stable-models and nondeterministic fixpoints. We show that with suitable storage structures, the differential fixpoint computation of our programs matches the complexity of procedural algorithms in classical search and optimization problems.

关键词： Datalog greedy algorithms query evaluation

来源：评论

学校读者我要写书评

暂无评论

greedy algorithms for Joint Sparse Recovery

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2014年第7期62卷 1694-1704页

作者： Blanchard, Jeffrey D. Cermak, Michael Hanle, David Jing, Yirong Grinnell Coll Dept Math & Stat Grinnell IA 50112 USA

Five known greedy algorithms designed for the single measurement vector setting in compressed sensing and sparse approximation are extended to the multiple measurement vector scenario: Iterative Hard Thresholding (IHT), Normalized IHT (NIHT), Hard Thresholding Pursuit (HTP), Normalized HTP (NHTP), and Compressive Sampling Matching Pursuit (CoSaMP). Using the asymmetric restricted isometry property (ARIP), sufficient conditions for all five algorithms establish bounds on the discrepancy between the algorithms' output and the optimal row-sparse representation. When the initial multiple measurement vectors are jointly sparse, ARIP-based guarantees for exact recovery are also established. The algorithms are then compared via the recovery phase transition framework. The strong phase transitions describing the family of Gaussian matrices which satisfy the sufficient conditions are obtained via known bounds on the ARIP constants. The algorithms' empirical weak phase transitions are compared for various numbers of multiple measurement vectors. Finally, the performance of the algorithms is compared against a known rank aware greedy algorithm, Rank Aware Simultaneous Orthogonal Matching Pursuit + MUSIC. Simultaneous recovery variants of NIHT, NHTP, and CoSaMP all outperform the rank-aware algorithm.

关键词： Compressed sensing greedy algorithms multiple measurement vectors joint sparsity row sparse matrices performance comparison

来源：评论

学校读者我要写书评

暂无评论

greedy algorithms with Weights for Construction of Partial Association Rules

引用

FUNDAMENTA INFORMATICAE 2009年第1期94卷 101-120页

作者： Moshkov, Mikhail Ju. Piliszczuk, Marcin Zielosko, Beata King Abdullah Univ Sci & Technol Div Math & Comp Sci & Engn Jeddah 21534 Saudi Arabia ING Bank Slaski SA PL-40086 Katowice Poland Univ Silesia Inst Comp Sci PL-41200 Sosnowiec Poland

This paper is devoted to the study of approximate algorithms for minimization of the total weight of attributes occurring in partial association rules. We consider mainly greedy algorithms with weights for construction of rules. The paper contains bounds on precision of these algorithms and bounds on the minimal weight of partial association rules based on an information obtained during the greedy algorithm run.

关键词： Rough sets information systems weights association rules greedy algorithms

来源：评论

学校读者我要写书评

暂无评论

greedy algorithms for Optimal Measurements Selection in State Estimation Using Reduced Models

引用

SIAM-ASA JOURNAL ON UNCERTAINTY QUANTIFICATION 2018年第3期6卷 1101-1126页

作者： Binev, Peter Cohen, Albert Mula, Olga Nichols, James Univ South Carolina Dept Math Columbia SC 29208 USA Sorbonne Univ Lab Jacques Louis Lions UMR 7598 4 Pl Jussieu F-75005 Paris France Univ Paris 09 PSL Univ CNRS UMR 7534CEREMADE F-75016 Paris France

We consider the problem of optimal recovery of an unknown function u in a Hilbert space V from measurements of the form l(j)(u), j = 1, . . . , m, where the l(j) are known linear functionals on V. We are motivated by the setting where u is a solution to a PDE with some unknown parameters, therefore lying on a certain manifold contained in V. Following the approach adopted in [Maday, Patera, Penn and Yano, Int. J. Namer. Methods Engrg., 102 (2015), pp. 933-965, Binev, Cohen, Dahmen, DeVore, Petrova, and Wojtaszczyk, SIAM J. Uncertainty Quantification, 5 (2017), pp. 1-29], the prior on the unknown function can be described in terms of its approximability by finitedimensional reduced model spaces (V-n)(n >= 1) where dim(V-n) = n. Examples of such spaces include classical approximation spaces, e.g., finite elements or trigonometric polynomials, as well as reduced basis spaces which are designed to match the solution manifold more closely. The error bounds for optimal recovery under such priors are of the form mu(V-n, W-m)epsilon(n), where s n is the accuracy of the reduced model V-n and mu(V-n, W-m) is the inverse of an inf-sup constant that describe the angle between V-n and the space W m spanned by the Riesz representers of (l(1), . . . , l(m)). This paper addresses the problem of properly selecting the measurement functionals, in order to control at best the stability constant mu(V-n, W-m), for a given reduced model space V-n. Assuming that the l(j) can be picked from a given dictionary D we introduce and analyze greedy algorithms that perform a suboptimal selection in reasonable computational time. We study the particular case of dictionaries that consist either of point value evaluations or local averages, as idealized models for sensors in physical systems. Our theoretical analysis and greedy algorithms may therefore be used in order to optimize the position of such sensors.

关键词： greedy algorithms data assimilation reduced models sensor placement inf-sup stability

来源：评论

学校读者我要写书评

暂无评论

greedy algorithms FOR THE MAXIMUM SATISFIABILITY PROBLEM: SIMPLE algorithms AND INAPPROXIMABILITY BOUNDS

引用

SIAM JOURNAL ON COMPUTING 2017年第3期46卷 1029-1061页

作者： Poloczek, Matthias Schnitger, Georg Williamson, David P. Van Zuylen, Anke Cornell Univ Sch Operat Res & Informat Engn Ithaca NY 14853 USA Goethe Univ Frankfurt Main Inst Comp Sci Frankfurt Germany Coll William & Mary Dept Math Williamsburg VA 23185 USA

We give a simple, randomized greedy algorithm for the maximum satisfiability problem (MAX SAT) that obtains a 3/4-approximation in expectation. In contrast to previously known 3/4-approximation algorithms, our algorithm does not use flows or linear programming. Hence we provide a positive answer to a question posed by Williamson in 1998 on whether such an algorithm exists. Moreover, we show that Johnson's greedy algorithm cannot guarantee a 3/4-approximation, even if the variables are processed in a random order. Thereby we partially solve a problem posed by Chen, Friesen, and Zheng in 1999. In order to explore the limitations of the greedy paradigm, we use the model of priority algorithms of Borodin, Nielsen, and Rackoff. Since our greedy algorithm works in an online scenario where the variables arrive with their set of undecided clauses, we wonder if a better approximation ratio can be obtained by further fine-tuning its random decisions. For a particular information model we show that no priority algorithm can approximate Online MAX SAT within 3/4 + epsilon (for any epsilon > 0). We further investigate the strength of deterministic greedy algorithms that may choose the variable ordering. Here we show that no adaptive priority algorithm can achieve approximation ratio 3/4. We propose two ways in which this inapproximability result can be bypassed. First we show that if our greedy algorithm is additionally given the variable assignments of an optimal solution to the canonical LP relaxation, then we can derandomize its decisions while preserving the overall approximation guarantee. Second we give a simple, deterministic algorithm that performs an additional pass over the input. We show that this 2-pass algorithm satisfies clauses with a total weight of at least 3/4 OPTLP, where OPTLP is the objective value of the canonical linear program. Moreover, we demonstrate that our analysis is tight and detail how each pass can be implemented in linear time.

关键词： approximation algorithms greedy algorithms maximum satisfiability problem priority algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

greedy algorithms for Hybrid Compressed Sensing

引用

IEEE SIGNAL PROCESSING LETTERS 2020年 27卷 2059-2063页

作者： Tai, Ching-Lun Hsieh, Sung-Hsien Lu, Chun-Shien Acad Sinica Inst Informat Sci Taipei 115 Taiwan

Compressed sensing (CS) is a technique which uses fewer measurements than dictated by the Nyquist sampling theorem. The traditional CS with linear measurements achieves effective recovery, but it suffers from large bit consumption due to the precision required by those measurements. Then, the one-bit CS with binary measurements is proposed to save the bit budget, but it is infeasible when the energy information of signals is not available as a prior knowledge. Subsequently, the hybrid CS which combines traditional CS and one-bit CS appears, striking a balance between the pros and cons of both types of CS. Given that one-bit CS is optimal for the direction estimation of signals under noise with a fixed bit budget and that traditional CS is able to provide residue information and estimated signals, we focus on the design of greedy algorithms, which consist of the main steps of support detection and recovered signal updates, for hybrid CS in this paper. We propose two greedy algorithms for hybrid CS, with traditional CS offering signal estimates and updated residues, which help one-bit CS detect the support iteratively. Then, we provide a theoretical analysis of the error bound between the normalized original signal and the normalized estimated signal. Numerical results demonstrate the efficacy of the proposed greedy algorithms for hybrid CS in noisy environments.

关键词： Error bound greedy algorithms hybrid compressed sensing (CS)

来源：评论

学校读者我要写书评

暂无评论

Universal bases and greedy algorithms for anisotropic function classes

引用

CONSTRUCTIVE APPROXIMATION 2002年第4期18卷 529-550页

作者： Temlyakov, VN Univ S Carolina Dept Math Columbia SC 29208 USA

We suggest a three-step strategy to find a good basis (dictionary) for nonlinear m-term approximation. The first step consists of solving an optimization problem of finding a near best basis for a given function class F, when we optimize over a collection D of bases (dictionaries). The second step is devoted to finding a universal basis (dictionary) D-u epsilon D for a given pair (F, D) of collections: F of function classes and D of bases (dictionaries). This means that D-u provides near optimal approximation for each class F from a collection T. The third step deals with constructing a theoretical algorithm that realizes near best m-term approximation with regard to D-u for function classes from F. In this paper we work this strategy out in the model case of anisotropic function classes and the set of orthogonal bases. The results are positive. We construct a natural tensor-product-wavelet-type basis and prove that it is universal. Moreover, we prove that a greedy algorithm realizes near best in-term approximation with regard to this basis for all anisotropic function classes.

关键词： best m-term approximation greedy algorithms thresholding optimization universality

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：