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...
详细信息
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.
Given a Banach space X and one of its compact sets , we consider the problem of finding a good n-dimensional space X (n) aS,X which can be used to approximate the elements of . The best possible error we can achieve f...
详细信息
Given a Banach space X and one of its compact sets , we consider the problem of finding a good n-dimensional space X (n) aS,X which can be used to approximate the elements of . The best possible error we can achieve for such an approximation is given by the Kolmogorov width . However, finding the space which gives this performance is typically numerically intractable. Recently, a new greedy strategy for obtaining good spaces was given in the context of the reduced basis method for solving a parametric family of PDEs. The performance of this greedy algorithm was initially analyzed in Buffa et al. (Mod,l. Math. Anal. Num,r. 46:595-603, 2012) in the case is a Hilbert space. The results of Buffa et al. (Mod,l. Math. Anal. Num,r. 46:595-603, 2012) were significantly improved upon in Binev et al. (SIAM J. Math. Anal. 43:1457-1472, 2011). The purpose of the present paper is to give a new analysis of the performance of such greedy algorithms. Our analysis not only gives improved results for the Hilbert space case but can also be applied to the same greedy procedure in general Banach spaces.
The article extends upon previous work by Temlyakov, Konyagin, and Wojtaszczyk on comparing the error of certain greedy algorithms with that of best m-term approximation with respect to a general biorthogonal system i...
详细信息
The article extends upon previous work by Temlyakov, Konyagin, and Wojtaszczyk on comparing the error of certain greedy algorithms with that of best m-term approximation with respect to a general biorthogonal system in a Banach space X. We consider both necessary and sufficient conditions which cover most of the special cases previously considered. Some new results concerning the Haar system in Li, L,. and BMO are also included.
Let X be a Banach space and K be a compact subset in X. We consider a greedy algorithm for finding n-dimensional subspace V-n subset of X which can be used to approximate the elements of K. We are interested in how we...
详细信息
Let X be a Banach space and K be a compact subset in X. We consider a greedy algorithm for finding n-dimensional subspace V-n subset of X which can be used to approximate the elements of K. We are interested in how well the space V-n approximates the elements of K. For this purpose we compare the performance of greedy algorithm measured by sigma(n)(K)(X) := dist(K, V-n)(X) with the Kolmogorov width d(n)(K)(X) which is the best possible error one can achieve when approximating K by n-dimensional subspaces. Various results in this direction have been given, e.g., in Binev et al. (2011), DeVore et al. (2013) and Wojtaszczyk (2015). The purpose of the present paper is to continue this line. We shall show that there exists a constant C > 0 such that sigma(n)(K)(X) <= Cn(-s+mu)(log(n + 1))(min(s,1/2)), n >= 1, if Kolmogorov widths d(n)(K)(X) decay as n(-s) and the Banach-Mazur distance between an arbitrary n-dimensional subspace V-n subset of X and l(2)(n) satisfies d(V-n, l(2)(n)) <= C(1)n(mu). In particular, when some additional information about the set K is given then there is no logarithmic factor in this estimate. (C) 2019 Elsevier Inc. All rights reserved.
We study greedy algorithms in a Banach space from the point of view of convergence and rate of convergence. We concentrate on studying algorithms that provide expansions into a series. We call such expansions greedy e...
详细信息
We study greedy algorithms in a Banach space from the point of view of convergence and rate of convergence. We concentrate on studying algorithms that provide expansions into a series. We call such expansions greedy expansions. It was pointed out in our previous article that there is a great flexibility in choosing coefficients of greedy expansions. In that article this flexibility was used for constructing a greedy expansion that converges in any uniformly smooth Banach space. In this article we push the flexibility in choosing the coefficients of greedy expansions to the extreme. We make these coefficients independent of an element f is an element of X. Surprisingly, for a properly chosen sequence of coefficients we obtain results similar to the previous results on greedy expansions when the coefficients were determined by an element f.
We study the problem of fairly allocating a set of indivisible goods among agents with additive valuations. The extent of fairness of an allocation is measured by its Nash social welfare, which is the geometric mean o...
详细信息
ISBN:
(纸本)9781450356497
We study the problem of fairly allocating a set of indivisible goods among agents with additive valuations. The extent of fairness of an allocation is measured by its Nash social welfare, which is the geometric mean of the valuations of the agents for their bundles. While the problem of maximizing Nash social welfare is known to be APX-hard in general, we study the effectiveness of simple, greedy algorithms in solving this problem in two interesting special cases. First, we show that a simple, greedy algorithm provides a 1.061-approximation guarantee when agents have identical valuations, even though the problem of maximizing Nash social welfare remains NP-hard for this setting. Second, we show that when agents have binary valuations over the goods, an exact solution (i.e., a Nash optimal allocation) can be found in polynomial time via a greedy algorithm. Our results in the binary setting extend to provide novel, exact algorithms for optimizing Nash social welfare under concave valuations. Notably, for the above mentioned scenarios, our techniques provide a simple alternative to several of the existing, more sophisticated techniques for this problem such as constructing equilibria of Fisher markets or using real stable polynomials.
Borodin et al. (Algorithmica 37(4):295-326, 2003) gave a model of greedy-like algorithms for scheduling problems and Angelopoulos and Borodin (Algorithmica 40(4):271-291, 2004) extended their work to facility location...
详细信息
Borodin et al. (Algorithmica 37(4):295-326, 2003) gave a model of greedy-like algorithms for scheduling problems and Angelopoulos and Borodin (Algorithmica 40(4):271-291, 2004) extended their work to facility location and set cover problems. We generalize their model to include other optimization problems, and apply the generalized framework to graph problems. Our goal is to define an abstract model that captures the intrinsic power and limitations of greedy algorithms for various graph optimization problems, as Borodin et al. (Algorithmica 37(4):295-326, 2003) did for scheduling. We prove bounds on the approximation ratio achievable by such algorithms for basic graph problems such as shortest path, weighted vertex cover, Steiner tree, and independent set. For example, we show that, for the shortest path problem, no algorithm in the FIXED priority model can achieve any approximation ratio (even one dependent on the graph size), but the well-known Dijkstra's algorithm is an optimal ADAPTIVE priority algorithm. We also prove that the approximation ratio for weighted vertex cover achievable by ADAPTIVE priority algorithms is exactly 2. Here, a new lower bound matches the known upper bounds (Johnson in J. Comput. Syst. Sci. 9(3):256-278, 1974). We give a number of other lower bounds for priority algorithms, as well as a new approximation algorithm for minimum Steiner tree problem with weights in the interval [1,2].
In this era of big data, many systems of interest to researchers are too large to fully sample. Thus, significant downsampling is necessary, but determining the best locations for optimal full-state reconstructions is...
详细信息
In this era of big data, many systems of interest to researchers are too large to fully sample. Thus, significant downsampling is necessary, but determining the best locations for optimal full-state reconstructions is an NP-hard problem. Solving for the optimal sensor selections would require the researcher to test all (np) combinations of placing p sensors given n possible locations, which is only feasible for very small systems. Instead, researchers have developed techniques to calculate near-optimal sensor placements, usually based on convex relaxations or greedy algorithms. This text focuses on a well-known greedy algorithm, the column-pivoted QR decomposition, which is performed on basis modes from a low-rank decomposition of the system, to pick out sensor locations that are approximately maximally informative and robust to noise. The column-pivoted QR decomposition is efficient and has proven optimality guarantees, but it does not account for several important practical considerations, including sensor cost, purpose, and type. In this work, we extend the QR decomposition to account for some of these real-world constraints. First, we modify the algorithm to account for a heterogeneous cost function on sensor location, selecting sensors that are approximately Pareto optimal in cost and reconstruction quality. Next, we demonstrate that the cost-constrained column-pivoted QR decomposition can be applied to modal bases beyond the most common basis of singular vectors. In this way, we can select sensors and actuators for control systems, account for a system's estimated equations of motion, and even select sensors without training data. Finally, we approach the problem of multi-fidelity sensor selection, that is, determining where and how many of each type of sensor to place, given a fixed budget and access to cheap, high-noise sensors and expensive, low-noise sensors. This problem is complex and has a very large parameter space, but we develop guidelines for asympt
In this paper we focus on increasing cybersecurity by means of greedy algorithms applied to network anomaly detection task. In particular, we propose to use Matching Pursuit and Orthogonal Matching Pursuit algorithms....
详细信息
ISBN:
(纸本)9783642330179
In this paper we focus on increasing cybersecurity by means of greedy algorithms applied to network anomaly detection task. In particular, we propose to use Matching Pursuit and Orthogonal Matching Pursuit algorithms. The major contribution of the paper is the proposition of 1D KSVD structured dictionary for greedy algorithm as well as its tree based structure representation (clusters). The promising results for 15 network metrics are reported and compared to DWT-based approach.
This paper examines the Aircraft Sequencing Problem (ASP) over multiple runways, under mixed mode operations with the objective of minimizing the total weighted tardiness of aircraft landings and departures simultaneo...
详细信息
This paper examines the Aircraft Sequencing Problem (ASP) over multiple runways, under mixed mode operations with the objective of minimizing the total weighted tardiness of aircraft landings and departures simultaneously. The ASP can be modeled as a parallel machine scheduling problem with unequal ready-times, target times and deadlines. Furthermore, sequence-dependent separation times on each runway are considered to prevent the dangers associated with wake-vortex effects. Due to the problem being NP-hard, greedy heuristics and metaheuristics are applied in this paper to obtain solutions in reasonable computation times. The algorithms' solutions are compared to optimal solutions and their performances are evaluated in terms of solution quality and CPU time. (C) 2013 Elsevier Ltd. All rights reserved.
暂无评论