Search results for "FACTORIZATION"
showing 10 items of 221 documents
Efficient Analysis and Synthesis Using a New Factorization of the Gabor Frame Matrix
2018
In this paper, we consider the case in which one needs to carry out Gabor analysis and synthesis on large signals using a short support analysis window and its corresponding, possibly longer canonical dual window, respectively. In this asymmetric context, we propose a novel factorization of the Gabor frame operator that exploits its strong and well-known structure and leads to a computational cost for synthesis, which is comparable to the one needed for short support analysis. The proposed factorization applies to any Gabor system with very mild conditions and leads to a potentially promising alternative to current synthesis algorithms in the case of short analysis windows whose support is …
Suffix array and Lyndon factorization of a text
2014
Abstract The main goal of this paper is to highlight the relationship between the suffix array of a text and its Lyndon factorization. It is proved in [15] that one can obtain the Lyndon factorization of a text from its suffix array. Conversely, here we show a new method for constructing the suffix array of a text that takes advantage of its Lyndon factorization. The surprising consequence of our results is that, in order to construct the suffix array, the local suffixes inside each Lyndon factor can be separately processed, allowing different implementative scenarios, such as online, external and internal memory, or parallel implementations. Based on our results, the algorithm that we prop…
cuBool: Bit-Parallel Boolean Matrix Factorization on CUDA-Enabled Accelerators
2018
Boolean Matrix Factorization (BMF) is a commonly used technique in the field of unsupervised data analytics. The goal is to decompose a ground truth matrix C into a product of two matrices A and $B$ being either an exact or approximate rank k factorization of C. Both exact and approximate factorization are time-consuming tasks due to their combinatorial complexity. In this paper, we introduce a massively parallel implementation of BMF - namely cuBool - in order to significantly speed up factorization of huge Boolean matrices. Our approach is based on alternately adjusting rows and columns of A and B using thousands of lightweight CUDA threads. The massively parallel manipulation of entries …
Archetypoids: A new approach to define representative archetypal data
2015
[EN] The new concept archetypoids is introduced. Archetypoid analysis represents each observation in a dataset as a mixture of actual observations in the dataset, which are pure type or archetypoids. Unlike archetype analysis, archetypoids are real observations, not a mixture of observations. This is relevant when existing archetypal observations are needed, rather than fictitious ones. An algorithm is proposed to find them and some of their theoretical properties are introduced. It is also shown how they can be obtained when only dissimilarities between observations are known (features are unavailable). Archetypoid analysis is illustrated in two design problems and several examples, compar…
Stochastic Learning for SAT- Encoded Graph Coloring Problems
2010
The graph coloring problem (GCP) is a widely studied combinatorial optimization problem due to its numerous applications in many areas, including time tabling, frequency assignment, and register allocation. The need for more efficient algorithms has led to the development of several GC solvers. In this paper, the authors introduce a team of Finite Learning Automata, combined with the random walk algorithm, using Boolean satisfiability encoding for the GCP. The authors present an experimental analysis of the new algorithm’s performance compared to the random walk technique, using a benchmark set containing SAT-encoding graph coloring test sets.
Searching for a strong double tracing in a graph
1998
Given a connected graph G, we present a polynomial algorithm which either finds a tour traversing each edge of G exactly two non-consecutive times, one in each direction, or decides that no such tour exists. The main idea of this algorithm is based on the modification of a proof given by Thomassen related to a problem proposed by Ore in 1951.
Tridiagonality, supersymmetry and non self-adjoint Hamiltonians
2019
In this paper we consider some aspects of tridiagonal, non self-adjoint, Hamiltonians and of their supersymmetric counterparts. In particular, the problem of factorization is discussed, and it is shown how the analysis of the eigenstates of these Hamiltonians produce interesting recursion formulas giving rise to biorthogonal families of vectors. Some examples are proposed, and a connection with bi-squeezed states is analyzed.
Time-dependent perturbation treatment of independent Raman schemes
2007
The problem of a trapped ion subjected to the action of two or more independent Raman schemes is analysed through a suitable time-dependent perturbative approach based on the factorization of the evolution operator in terms of other unitary operators. We show that the dynamics of the system may be traced back to an effective Hamiltonian up to a suitable dressing. Moreover, we give the method to write the master equation corresponding to the case wherein spontaneous decays occur.
Learning to Rank Images for Complex Queries in Concept-based Search
2018
Concept-based image search is an emerging search paradigm that utilizes a set of concepts as intermediate semantic descriptors of images to bridge the semantic gap. Typically, a user query is rather complex and cannot be well described using a single concept. However, it is less effective to tackle such complex queries by simply aggregating the individual search results for the constituent concepts. In this paper, we propose to introduce the learning to rank techniques to concept-based image search for complex queries. With freely available social tagged images, we first build concept detectors by jointly leveraging the heterogeneous visual features. Then, to formulate the image relevance, …
Factorization of strongly (p,sigma)-continuous multilinear operators
2013
We introduce the new ideal of strongly-continuous linear operators in order to study the adjoints of the -absolutely continuous linear operators. Starting from this ideal we build a new multi-ideal by using the composition method. We prove the corresponding Pietsch domination theorem and we present a representation of this multi-ideal by a tensor norm. A factorization theorem characterizing the corresponding multi-ideal - which is also new for the linear case - is given. When applied to the case of the Cohen strongly -summing operators, this result gives also a new factorization theorem.