Search

In this work, we revisit fast dimension reduction approaches, as with random projections and random sampling. Our goal is to summarize the data to decrease computational costs and memory footprint of subsequent analysis. Such dimension reduction can be very efficient when the signals of interest have a strong structure, such as with images. We focus on this setting and investigate feature clustering schemes for data reductions that capture this structure. An impediment to fast dimension reduction is then that good clustering comes with large algorithmic costs. We address it by contributing a linear-time agglomerative clustering scheme, Recursive Nearest Agglomeration (ReNA). Unlike existing fast agglomerative schemes, it avoids the creation of giant clusters. We empirically validate that it approximates the data as well as traditional variance-minimizing clustering schemes that have a quadratic complexity. In addition, we analyze signal approximation with feature clustering and show that it can remove noise, improving subsequent analysis steps. As a consequence, data reduction by clustering features with ReNA yields very fast and accurate models, enabling to process large datasets on budget. Our theoretical analysis is backed by extensive experiments on publicly-available data that illustrate the computation efficiency and the denoising properties of the resulting dimension reduction scheme. [ABSTRACT FROM AUTHOR]

The bilateral filter is a non-linear filter that uses a range filter along with a spatial filter to perform edge-preserving smoothing of images. A direct computation of the bilateral filter requires $O(S)$ operations per pixel, where $S$ is the size of the support of the spatial filter. In this paper, we present a fast and provably accurate algorithm for approximating the bilateral filter when the range kernel is Gaussian. In particular, for box and Gaussian spatial filters, the proposed algorithm can cut down the complexity to $O(1)$ per pixel for any arbitrary $S$ . The algorithm has a simple implementation involving $N+1$ spatial filterings, where $N$ is the approximation order. We give a detailed analysis of the filtering accuracy that can be achieved by the proposed approximation in relation to the target bilateral filter. This allows us to estimate the order $N$ required to obtain a given accuracy. We also present comprehensive numerical results to demonstrate that the proposed algorithm is competitive with the state-of-the-art methods in terms of speed and accuracy. [ABSTRACT FROM AUTHOR]

The problem of partial occlusion in face recognition has received less attention over the last few years. Partial occlusion is an important challenge of the face recognition, in which certain parts of a face are hidden by the objects such as sunglasses, hats, scarves, and a mask that can cause significant degradation in the performance of the recognition system. This paper specifically addresses face recognition with partial occlusion. The proposed algorithm is an approximate version of conventional dynamic time warping (DTW), which is an exact algorithm and based on dynamic programming. An exact algorithm provides an exact result and involves huge computation efforts when there is a gallery with more images. Hence, a faster approximation algorithm based on greedy approach is proposed to solve the partially occluded face recognition problem by finding a near optimal solution with a guarantee on its performance. Many image processing applications are real-time and need a near-optimal solution. The proposed work has two contributions, the first one is in designing a string generation algorithm for converting a face into a sequence of strings and the second is designing an approximation algorithm based on greedy approach for matching strings. The proposed work uses standard face databases such as FEI, IAB, ORL, and Extended Yale-B for evaluating the effectiveness of the system. [ABSTRACT FROM AUTHOR]

The bilateral and nonlocal means filters are instances of kernel-based filters that are popularly used in image processing. It was recently shown that fast and accurate bilateral filtering of grayscale images can be performed using a low-rank approximation of the kernel matrix. More specifically, based on the eigendecomposition of the kernel matrix, the overall filtering was approximated using spatial convolutions, for which efficient algorithms are available. Unfortunately, this technique cannot be scaled to high-dimensional data such as color and hyperspectral images. This is simply because one needs to compute/store a large matrix and perform its eigendecomposition in this case. We show how this problem can be solved using the Nystr $\ddot{\text{o}}$ m method, which is generally used for approximating the eigendecomposition of large matrices. The resulting algorithm can also be used for nonlocal means filtering. We demonstrate the effectiveness of our proposal for bilateral and nonlocal means filtering of color and hyperspectral images. In particular, our method is shown to be competitive with state-of-the-art fast algorithms, and moreover, it comes with a theoretical guarantee on the approximation error. [ABSTRACT FROM AUTHOR]

Multiple-view triangulation by $\ell _\infty$ minimisation has become established in computer vision. State-of-the-art $\ell _\infty$ triangulation algorithms exploit the quasiconvexity of the cost function to derive iterative update rules that deliver the global minimum. Such algorithms, however, can be computationally costly for large problem instances that contain many image measurements, e.g., from web-based photo sharing sites or long-term video recordings. In this paper, we prove that $\ell _\infty$ triangulation admits a coreset approximation scheme, which seeks small representative subsets of the input data called coresets. A coreset possesses the special property that the error of the $\ell _\infty$ solution on the coreset is within known bounds from the global minimum. We establish the necessary mathematical underpinnings of the coreset algorithm, specifically, by enacting the stopping criterion of the algorithm and proving that the resulting coreset gives the desired approximation accuracy. On large-scale triangulation problems, our method provides theoretically sound approximate solutions. Iterated until convergence, our coreset algorithm is also guaranteed to reach the true optimum. On practical datasets, we show that our technique can in fact attain the global minimiser much faster than current methods. [ABSTRACT FROM AUTHOR]

In this paper, we consider a variant of dominating set problem, i.e., the total dominating set problem. Given an undirected graph G = (V , E) , a subset of vertices T ⊆ V is called a total dominating set if every vertex in V is adjacent to at least one vertex in T. Based on LP relaxation techniques, this paper gives a distributed approximation algorithm for the total dominating set problem in general graphs. The presented algorithm obtains a fractional total dominating set that is, at most, k (1 + Δ 1 k) Δ 1 k times the size of the optimal solution to this problem, where k is a positive integer and Δ is the maximum degree of G. The running time of this algorithm is constant communication rounds under the assumption of a synchronous communication model. [ABSTRACT FROM AUTHOR]

The piecewise monotonic approximation problem makes the least changes to n univariate noisy data so that the piecewise linear interpolant to the new values is composed of at most k monotonic sections. The term "least changes" is defined in the sense of a global sum of strictly convex functions of changes. The main difficulty in this calculation is that the extrema of the interpolant have to be found automatically, but the number of all possible combinations of extrema can be O (n k - 1) , which makes not practicable to test each one separately. It is known that the case k = 1 is straightforward, and that the case k > 1 reduces to partitioning the data into at most k disjoint sets of adjacent data and solving a k = 1 problem for each set. Some ordering relations of the extrema are studied that establish three quite efficient algorithms by using a binary search method for partitioning the data. In the least squares case the total work is only O (n σ + k σ log 2 σ) computer operations when k ≥ 3 and is only O (n) when k = 1 or 2, where σ - 2 is the number of sign changes in the sequence of the first differences of the data. Fortran software has been written for this case and the numerical results indicate superior performance to existing algorithms. Some examples with real data illustrate the method. Many applications of the method arise from bioinformatics, energy, geophysics, medical imaging, and peak finding in spectroscopy, for instance. [ABSTRACT FROM AUTHOR]

The basic aim of this work is to design a new tridiagonal matrix enhanced multivariance products representation (TMEMPR) which uses not Cartesian vectors but matrices as the support entities. What we obtain after the construction of the representation has been a singular value decomposition like structure where the core matrix becomes a block tridiagonal matrix in contrast to the diagonal and tridiagonal matrix structures of the singular value decomposition of matrices and TMEMPR respectively. We have used support matrices in the construction and not directly orthogonality of the constructed support matrices but block orthogonality which means the mutual ortho normality of the columns of produced support matrices. Certain confirmative implementations finalize the paper. [ABSTRACT FROM AUTHOR]

In this article, we address the problem of approximating data points by C-smooth polynomial spline curves or surfaces using L-norm. The use of this norm helps to preserve the data shape and it reduces extraneous oscillations. In our approach, we introduce a new functional which enables to control directly the distance between the data points and the resulting spline solution. The computational complexity of the minimization algorithm is nonlinear. A local minimization method using sliding windows allows to compute approximation splines within a linear complexity. This strategy seems to be more robust than a global method when applied on large data sets. When the data are noisy, we iteratively apply this method to globally smooth the solution while preserving the data shape. This method is applied to image denoising. [ABSTRACT FROM AUTHOR]

In this paper, we study the spectrum assignment problem for wireless access networks. We assume that each secondary user will bid a certain value for exclusive usage of some spectrum channels for a certain time period or for a certain time duration. A secondary user may also require the exclusive usage of a subset of channels, or require the exclusive usage of a certain number of channels. Thus, several versions of problems are formulated under various different assumptions. For the majority of problems, we design PTAS or efficient constant-approximation algorithms such that overall profit is maximized. Here, the profit is defined as the total bids of all satisfied secondary users. As a side product of our algorithms, we are able to show that a previously studied Scheduling Split Interval Problem (SSIP) [CHECK END OF SENTENCE], in which each job is composed of t intervals, cannot be approximated within O(t^1-\epsilon ) for any small \epsilon >0 unless NP=ZPP. Opportunistic spectrum usage, although a promising technology, could suffer from the selfish behavior of secondary users. In order to improve opportunistic spectrum usage, we then propose to combine the game theory with wireless modeling. We show how to design a truthful mechanism based on all of these algorithms such that the best strategy of each secondary user to maximize its own profit is to truthfully report its actual bid. [ABSTRACT FROM AUTHOR]