Search

Cross-validation (CV) is a widely adopted approach for selecting the optimal model. However, the computation of empirical cross-validation error (CVE) has high complexity due to multiple times of learner training. In this paper, we develop a novel approximation theory of CVE and present an approximate approach to CV based on the Bouligand influence function (BIF) for kernel-based algorithms. We first represent the BIF and higher order BIFs in Taylor expansions, and approximate CV via the Taylor expansions. We then derive an upper bound of the discrepancy between the original and approximate CV. Furthermore, we provide a novel computing method to calculate the BIF for general distribution, and evaluate BIF criterion for sample distribution to approximate CV. The proposed approximate CV requires training on the full data set only once and is suitable for a wide variety of kernel-based algorithms. Experimental results demonstrate that the proposed approximate CV is sound and effective. [ABSTRACT FROM AUTHOR]

This paper introduces an efficient algorithm for finding the dominant generalized eigenvectors of a pair of symmetric matrices. Combining tools from approximation theory and convex optimization, we develop a simple scalable algorithm with strong theoretical performance guarantees. More precisely, the algorithm retains the simplicity of the well-known power method but enjoys the asymptotic iteration complexity of the powerful Lanczos method. Unlike these classic techniques, our algorithm is designed to decompose the overall problem into a series of subproblems that only need to be solved approximately. The combination of good initializations, fast iterative solvers, and appropriate error control in solving the subproblems lead to a linear running time in the input sizes compared to the superlinear time for the traditional methods. The improved running time immediately offers acceleration for several applications. As an example, we demonstrate how the proposed algorithm can be used to accelerate canonical correlation analysis, which is a fundamental statistical tool for learning of a low-dimensional representation of high-dimensional objects. Numerical experiments on real-world datasets confirm that our approach yields significant improvements over the current state of the art. [ABSTRACT FROM AUTHOR]

This paper tackles the problem of millimeter-wave (mmWave) channel estimation in massive MIMO communication systems. A new Bayes-optimal channel estimator is derived using recent advances in the approximate belief propagation Bayesian inference paradigm. By leveraging the inherent sparsity of the mmWave MIMO channel in the angular domain, we recast the underlying channel estimation problem into that of reconstructing a compressible signal from a set of noisy linear measurements. Then, the generalized approximate message passing (GAMP) algorithm is used to find the entries of the unknown mmWave MIMO channel matrix. Unlike all the existing works on the same topic, we model the angular-domain channel coefficients by Laplacian distributed random variables. Furthermore, we establish the closed-form expressions for the various statistical quantities that need to be updated iteratively by GAMP. To render the proposed algorithm fully automated, we also develop an expectation-maximization (EM) based procedure that can be easily embedded within GAMP’s iteration loop in order to learn all the unknown parameters of the underlying Bayesian inference problem. The computer simulations show that the proposed combined EM-GAMP algorithm under a Laplacian prior exhibits improvements both in terms of channel estimation accuracy, achievable rate, and computational complexity, as compared to the Gaussian mixture prior that has been advocated in the recent literature. In addition, it is found that the Laplacian prior speeds up the convergence time of GAMP over the entire signal-to-noise ratio range. [ABSTRACT FROM AUTHOR]

Attribute subset selection is an important issue in data mining and information processing. However, most automatic methodologies consider only the relevance factor between samples while ignoring the diversity factor. This may not allow the utilization value of hidden information to be exploited. For this reason, we propose a hybrid model named intuitionistic fuzzy (IF) rough set to overcome this limitation. The model combines the technical advantages of rough set and IF set and can effectively consider the above-mentioned statistical factors. First, fuzzy information granules based on IF relations are defined and used to characterize the hierarchical structures of the lower and upper approximations of IF rough set within the framework of granular computing. Then, the computation of IF rough approximations and knowledge reduction in IF information systems are investigated. Third, based on the approximations of IF rough set, significance measures are developed to evaluate the approximation quality and classification ability of IF relations. Furthermore, a forward heuristic algorithm for finding one optimal reduct of IF information systems is developed using these measures. Finally, numerical experiments are conducted on public datasets to examine the effectiveness and efficiency of the proposed algorithm in terms of the number of selected attributes, computational time, and classification accuracy. [ABSTRACT FROM AUTHOR]

Milano Retinex is a family of spatial color algorithms inspired by Retinex and mainly devoted to the image enhancement. In the so-called point-based sampling Milano Retinex algorithms, this task is accomplished by processing the color of each image pixel based on a set of colors sampled in its surround. This paper presents STAR, a segmentation based approximation of the point-based sampling Milano Retinex approaches: it replaces the pixel-wise image sampling by a novel, computationally efficient procedure that detects once for all the color and spatial information relevant to image enhancement from clusters of pixels output by a segmentation. The experiments reported here show that STAR performs similarly to previous point-based sampling Milano Retinex approaches and that STAR enhancement improves the accuracy of the well-known algorithm scale-invariant feature transform on the description and matching of photographs captured under difficult light conditions. [ABSTRACT FROM AUTHOR]

Non-orthogonal multiple access (NOMA)-based cognitive wireless networks can improve the spectral efficiency to utilize the vacant spectrum resource and exploit the power domain diversity. In this paper, we formulate a max-min resource allocation problem for video traffic in NOMA-based cognitive wireless networks as a mixed integer non-linear programming (MINLP) problem. The max-min video transmission problem is subject to the constraints of maximum accessed user number at each subchannel, total available energy of each secondary user, video encoding characteristics, and interference power threshold. To solve the formulated MINLP problem, we divide it into two subproblems, i.e., a power allocation and secondary user scheduling subproblem, and a video packet scheduling subproblem. First, we apply a successive convex approximation to transform the joint power allocation and secondary user scheduling subproblem into a bi-convex programming problem. Second, the binary search and dual decomposition methods are combined to obtain the approximated optimal power allocation and secondary user scheduling solutions. Finally, we propose a heuristic packet scheduling algorithm. Simulation numerical results show that the proposed algorithm improves the video quality and guarantees the fairness among different secondary users. [ABSTRACT FROM AUTHOR]

We propose a mixed “skeleton” and “equivalence” nested approximation method to compress the impedance matrix of the method of moments for the wideband multiscale simulations. We first introduce a nested skeleton approximation, where the impedance matrix is expressed recursively by sampling the dominant basis functions (e. g., skeletons) with a fully algebraic implementation from the original basis functions. The idea is to introduce the automatically constructed test surface around the interface between near- and far-field regions, for each group the dominant RWGs are sampled recursively with the adaptive cross approximation to compress the matrix against the test surface. Second, we introduce a mixed-form algorithm of “skeleton” and “equivalence” nested approximation method, at low levels, the nested skeleton approximation is employed, and it is smoothly transferred to standard wideband nested equivalence approximation (WNESA) at high levels. An accurate number of skeletons can be always found with a predetermined threshold at a low level, which will improve computation efficiency, with respect to WNESA. The computational complexity of the proposed algorithm is $\mathcal {O}(N\log {N})$ , $N$ is the number of unknowns. Numerical wideband multiscale simulations demonstrate the efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

A physics-based rank-revealing multilevel algorithm to more efficiently compute low-rank (LR) approximations of the method of moments matrix blocks ${\mathbf{Z}}^{\textrm {os}}$ is presented. Using surface subsets of volumetric nonuniform spherical grids (proxy grids), an LR approximation ${\mathbf{Z}}^{\textrm {os}}\approx {\mathbf{AB}}^{\dagger }$ is obtained in two stages: 1) an upward pass and a downward pass on a multilevel tree, via truncated singular value decomposition-based analyses of interactions between source subclusters and their attendant proxy grids, rapidly estimates the rank and yields a domain of ${\mathbf{Z}}^{\textrm {os}}$ , in the form of a matrix ${\mathbf{B}}$ with orthonormal columns and 2) a fast matrix–matrix multiplication step yields ${\mathbf{A}}$. The algorithm reduces the ${\mathcal{ O}}(N^{3})$ computational costs of revealing the rank to ${\mathcal{ O}}(N^{2})$ or ${\mathcal{ O}}(N^{3/2})$ operations and that of finding an LR approximation to ${\mathcal{ O}}(N^{2})$ or ${\mathcal{ O}}(N^{3/2}\log N)$ operations by adopting enclosing or belt-like proxy grids for electromagnetically large basis/testing function distributions that are either densely packed in a volume or quasi-planar, respectively. [ABSTRACT FROM AUTHOR]

Recently, by taking advantage of evolutionary multiobjective optimization techniques in diversity preservation, the means of multiobjectivization has attracted increasing interest in the studies of multimodal optimization (MMO). While most existing work of multiobjectivization aims to find all optimal solutions simultaneously, in this paper, we propose to approximate multimodal fitness landscapes via multiobjectivization, thus providing an estimation of potential optimal areas. To begin with, an MMO problem is transformed into a multiobjective optimization problem (MOP) by adding an adaptive diversity indicator as the second optimization objective, and an approximate fitness landscape is obtained via optimization of the transformed MOP using a multiobjective evolutionary algorithm. Then, on the basis of the approximate fitness landscape, an adaptive peak detection method is proposed to find peaks where optimal solutions may exist. Finally, local search is performed inside the detected peaks on the approximate fitness landscape. To assess the performance of the proposed algorithm, extensive experiments are conducted on 20 multimodal test functions, in comparison with three state-of-the-art algorithms for MMO. Experimental results demonstrate that the proposed algorithm not only shows promising performance in benchmark comparisons, but also has good potential in assisting preference-based decision-making in MMO. [ABSTRACT FROM AUTHOR]

This paper presents an approximate minimum mean squared error (MMSE) adaptive beam-pattern design (ABD) method for MIMO active sensing systems. The proposed approximate MMSE ABD method leverages the physics of the MIMO arrays to provide a linear-Gaussian approximation that is specific to MIMO active sensing systems, and yields a computationally simple optimization problem. Computational complexity analysis confirms this theoretical reduction in the number of floating-point operations required, most notably that evaluation of the proposed approximate optimization cost function grows polynomially with the number of targets being tracked, whereas for evaluation of the exact cost the growth is exponential. Additionally, numerical results indicate that, even for a simple scenario with a single target being tracked, the proposed approximate MMSE ABD method does indeed reduce the mean squared error of target parameter estimation compared to the nonadaptive case, with a reduction in computation time of four orders of magnitude compared to exact MMSE ABD. [ABSTRACT FROM AUTHOR]

In this paper, we present a new low-complexity iterative joint phase estimation and decoding algorithm which can be applied to low-density-parity-check (or turbo) codes for channels affected by strong phase noise. The algorithm exhibits a very good performance and a very low complexity even in strong phase noise, high code rate, and high-order constellations. The proposed algorithm works by first obtaining a preliminary pilots-aided phase estimation. Next, the expressions for the belief propagation messages are approximated around that reference and reduced to a Gaussian canonical form. This results in a simple closed form of a recursive update. Simulations results for phase-shift-keying modulation of size 8 and quadrature-amplitude modulation of size 64 are presented and compared with other algorithms in the literature. [ABSTRACT FROM AUTHOR]

High efficiency video coding (HEVC) fractional interpolation algorithm has very high computational complexity. In this paper, two approximate HEVC fractional interpolation filters are proposed. They significantly reduce computational complexity of HEVC fractional interpolation with a negligible PSNR loss and bit rate increase. In addition, two approximate HEVC fractional interpolation hardware are proposed. They, in the worst case, can process 45 quad full HD (${3840\times 2160}$) fps. They consume up to 67.1% less energy than original HEVC fractional interpolation hardware. Therefore, they can be used in consumer electronics products that require a low energy HEVC encoder. [ABSTRACT FROM AUTHOR]

We propose a novel online learning paradigm for nonlinear-function estimation tasks based on the iterative projections in the $L^2$ space with probability measure reflecting the stochastic property of input signals. The proposed learning algorithm exploits the reproducing kernel of the so-called dictionary subspace, based on the fact that any finite-dimensional space of functions has a reproducing kernel characterized by the Gram matrix. The $L^2$ -space geometry provides the best decorrelation property in principle. The proposed learning paradigm is significantly different from the conventional kernel-based learning paradigm in two senses: first, the whole space is not a reproducing kernel Hilbert space; and second, the minimum mean squared error estimator gives the best approximation of the desired nonlinear function in the dictionary subspace. It preserves efficiency in computing the inner product as well as in updating the Gram matrix when the dictionary grows. Monotone approximation, asymptotic optimality, and convergence of the proposed algorithm are analyzed based on the variable-metric version of adaptive projected subgradient method. Numerical examples show the efficacy of the proposed algorithm for real data over a variety of methods including the extended Kalman filter and many batch machine-learning methods such as the multilayer perceptron. [ABSTRACT FROM AUTHOR]

Independent Component Analysis (ICA) is a technique for unsupervised exploration of multichannel data that is widely used in observational sciences. In its classic form, ICA relies on modeling the data as linear mixtures of nonGaussian independent sources. The maximization of the corresponding likelihood is a challenging problem if it has to be completed quickly and accurately on large sets of real data. This problem has been addressed by resorting to quasi-Newton methods, which rely on sparse approximations of the Hessian of the log-likelihood. However, those approximations are not accurate when the ICA model does not hold exactly, as is often the case for real datasets. We propose a new algorithm, dubbed Picard, which makes use of sparse approximate Hessians only as a preconditioner to the L-BFGS algorithm, refining the Hessian approximation from a memory of the past iterates. Extensive numerical comparisons to several algorithms of the same class demonstrate the superior performance of the proposed technique, especially on real data. [ABSTRACT FROM AUTHOR]

Wireless power transfer technology has witnessed huge development because of its convenience and reliability. This paper concerns the fundamental issue of wireless charger PLacement with Optimized charging uTility (PLOT), i.e., given a fixed number of chargers and a set of points where rechargeable devices can be placed with orientations uniformly distributed in the range of $[0, 2\pi)$ positions and orientations of chargers such that the overall expected charging utility for all points is maximized. To address PLOT, we propose a $1-1/e-\epsilon $ approximation algorithm. First, we present techniques to approximate the nonlinear charging power and the expected charging utility to make the problem almost linear. Second, we develop a dominating coverage set extraction method to reduce the continuous search space of PLOT to a limited and discrete one without a performance loss. Third, we prove that the reformulated problem is essentially maximizing a monotone submodular function subject to a matroid constraint, and propose a greedy algorithm to address this problem. We conduct both simulation and field experiments to validate our theoretical results, and the results show that our algorithm can outperform comparison algorithms by at least 32.9%. [ABSTRACT FROM AUTHOR]

While the proper orthogonal decomposition (POD) is optimal under certain norms, its also expensive to compute. For large matrix sizes, the QR decomposition provides a tractable alternative. Under the assumption that it is a rank-revealing QR (RRQR), the approximation error incurred is similar to the POD error; furthermore, the authors show the existence of an RRQR with exactly the same error estimate as POD. To numerically realize an RRQR decomposition, they discuss the (iterative) modified Gram Schmidt with pivoting and reduced basis methods. They show that these two seemingly different approaches are equivalent. They then describe an MPI/OpenMP parallel code that implements one of the QR-based model reduction algorithms analyzed, and document the codes scalability for large problems, such as gravitational waves, and demonstrate excellent scalability up to 32,768 cores and, for complex dense matrices, as large as 10,000x3,276,800. [ABSTRACT FROM AUTHOR]

Arising in connection with multiobjective selection and archiving, the hypervolume subset selection problem (HSSP) consists in finding a subset of size k\leq n of a set X\subset \mathbb R^d of n nondominated points in d -dimensional space that maximizes the hypervolume indicator. The incremental greedy approximation to the HSSP has an approximation guarantee of 1-1/e , and is polynomial in n and k , while no polynomial exact algorithms are known for d\geq 3 . The decremental greedy counterpart has no known approximation guarantee, but is potentially faster for large k , and still leads to good approximations in practice. The computation and update of individual hypervolume contributions are at the core of the implementation of this greedy strategy. In this paper, new algorithms for the computation and update of hypervolume contributions are developed. In three dimensions, updating the total hypervolume and all individual contributions under single-point changes is performed in linear time, while in the 4-D case all contributions are computed in O(n^2) time. As a consequence, the decremental greedy approximation to the HSSP can now be obtained in O(n(n-k) + n\log n) and O(n^2(n-k)) time for d=3 and d=4 , respectively. Experimental results show that the proposed algorithms significantly outperform existing ones. [ABSTRACT FROM AUTHOR]

The DC Power Flow approximation has been widely used for decades in both industry and academia due to its computational speed and simplicity, but suffers from inaccuracy, in part due to the assumption of a lossless network. This paper presents a natural extension of the DC Power Flow to lossy networks. Our approach is based on reformulating the lossy active power flow equations into a novel fixed-point equation, and iterating this fixed-point mapping to generate a sequence of improving estimates for the active power flow solution. Each iteration requires the solution of a standard DC Power Flow problem with a modified vector of power injections. The first iteration returns the standard DC Power Flow, and one or two additional iterations yields a one or two order-of-magnitude improvement in accuracy. For radial networks, we give explicit conditions on the power flow data which guarantee that the active power flow equations possess a unique solution, and that our iteration converges exponentially and monotonically to this solution. For meshed networks, we extensively test our results via standard power flow cases. [ABSTRACT FROM PUBLISHER]

Sweep coverage plays an important role in many applications like data gathering, sensing coverage, and devices control. In this paper, we deal with the sweep coverage problem with multiple mobile sensors to periodically cover n targets in the surveillance region. We propose three constant-factor approximations, namely, CycleSplit, HeteroCycleSplit, and PathSplit, to minimize the longest sweep period of mobile sensors under different scenarios, respectively. CycleSplit deals with the min-period sweep coverage problem (MPSC), in which each mobile sensor works independently along a predetermined trajectory cycle. It has an approximation ratio of (5-{2}/({n-m+1})) , which improves the best known approximation ratio of 5. HeteroCycleSplit is a 5\alpha $ -approximation. It computes the sensor routes for heterogeneous velocity min-period sweep coverage problem (HVMPSC), where each mobile sensor has a different velocity. PathSplit is a 2-approximation for connected path min-period sweep coverage problem (CPMPSC). It solves a variant problem of sweep coverage where we need to cover all the given edges. Besides, we also propose an optimal algorithm DP-MPSC for min-period sweep coverage problem in 1-D case. Finally, we provide various numerical experiments and comparisons with several previous work to validate the efficiency of our design. [ABSTRACT FROM AUTHOR]

This paper examines the applicability of hierarchical-matrices (H-matrices) to a computation of the demagnetizing field, which is the most time-consuming part in the micromagnetic simulation of spin torque oscillators (STO). Given that the kernel function of the convolution integral operator for the demagnetizing field has a second-order singularity, efficient approximation cannot be expected using conventional H-matrices employing adaptive cross approximation as the low-rank approximation. We introduce improved H-matrices to overcome this challenge. Furthermore, matrix sizes appearing in STO simulations are relatively small compared with the usual sizes of H-matrices. Through numerical experiments, we confirm the size conditions for memory usage and the computational time of H-matrix-vector products to demonstrate the advantages of using H-matrices. [ABSTRACT FROM AUTHOR]

This paper proposes a new framework for digital image processing; it relies on inexact computing to address some of the challenges associated with the discrete cosine transform (DCT) compression. The proposed framework has three levels of processing; the first level uses approximate DCT for image compressing to eliminate all computational intensive floating-point multiplications and executing the DCT processing by integer additions and in some cases logical right/left shifts. The second level further reduces the amount of data (from the first level) that need to be processed by filtering those frequencies that cannot be detected by human senses. Finally, to reduce power consumption and delay, the third level introduces circuit level inexact adders to compute the DCT. For assessment, a set of standardized images are compressed using the proposed three-level framework. Different figures of merits (such as energy consumption, delay, power-signal-to-noise-ratio, average-difference, and absolute-maximum-difference) are compared to existing compression methods; an error analysis is also pursued confirming the simulation results. Results show very good improvements in reduction for energy and delay, while maintaining acceptable accuracy levels for image processing applications. [ABSTRACT FROM AUTHOR]

It is known that polar codes can be efficiently constructed for binary-input channels. At the same time, existing algorithms for general input alphabets are less practical because of high complexity. We address the construction problem for the general case, and analyze an algorithm that is based on successive reduction of the output alphabet size of the subchannels in each recursion step. For this procedure, we estimate the approximation error as O(\mu ^-1/(q-1)) , where q is the input alphabet size and \mu is the “quantization parameter,” i.e., the maximum size of the subchannel output alphabet allowed by the algorithm. The complexity of the code construction scales as O(N\mu ^2 \log \mu) , where N is the length of the code. We also show that if the polarizing operation relies on modulo- $q$ addition, it is possible to merge subsets of output symbols without any loss in subchannel capacity. Performing this procedure before each approximation step results in a further speed-up of the code construction, and the resulting codes have smaller gap to capacity. We also show that a similar acceleration can be attained for polar codes over finite field alphabets. Experimentation shows that the suggested construction algorithms can be used to construct long polar codes for alphabets of size $q=16$ and more with acceptable loss of the code rate for a variety of polarizing transforms. [ABSTRACT FROM PUBLISHER]

We propose a novel nearest-neighbors approach to organize and curb the growth of radial basis function network in kernel adaptive filtering (KAF). The nearest-instance-centroid-estimation (NICE) kernel least-mean-square (KLMS) algorithm provides an appropriate time-space tradeoff with good performance. Its centers in the input/feature space are organized by quasi-orthogonal regions for greatly simplified filter evaluation. Instead of using all centers to evaluate/update the function approximation at every new point, a linear search among the iteratively-updated centroids determines the partial function to be used, naturally forming locally-supported partial functionals. Under this framework, partial functionals that compose the adaptive filter are quickly stored/retrieved based on input, each corresponding to a specialized “spatial-band” subfilter. The filter evaluation becomes the update of one of the subfilters, creating a content addressable filter bank (CAFB). This CAFB is incrementally updated for new signal applications with mild constraints, always using the past-learned partial filter sums, opening the door for transfer learning and significant efficiency for new data scenarios, avoiding training from scratch as have been done since the invention of adaptive filtering. Using energy conservation relation, we show the sufficient condition for mean square convergence of the NICE-KLMS algorithm and establish the upper and lower bounds of steady-state excess-mean-square-error (EMSE). Simulations on chaotic time-series prediction demonstrate similar levels of accuracy as existing methods, but with much faster computation involving fewer input samples. Simulations on transfer learning using both synthetic and real-world data demonstrate that NICE CAFB can leverage previously learned knowledge to related task or domain. [ABSTRACT FROM AUTHOR]

Deep learning has gained great popularity due to its widespread success on many inference problems. We consider the application of deep learning to the sparse linear inverse problem, where one seeks to recover a sparse signal from a few noisy linear measurements. In this paper, we propose two novel neural-network architectures that decouple prediction errors across layers in the same way that the approximate message passing (AMP) algorithms decouple them across iterations: through Onsager correction. First, we propose a “learned AMP” network that significantly improves upon Gregor and LeCun's “learned ISTA.” Second, inspired by the recently proposed “vector AMP” (VAMP) algorithm, we propose a “learned VAMP” network that offers increased robustness to deviations in the measurement matrix from i.i.d. Gaussian. In both cases, we jointly learn the linear transforms and scalar nonlinearities of the network. Interestingly, with i.i.d. signals, the linear transforms and scalar nonlinearities prescribed by the VAMP algorithm coincide with the values learned through back-propagation, leading to an intuitive interpretation of learned VAMP. Finally, we apply our methods to two problems from 5G wireless communications: compressive random access and massive-MIMO channel estimation. [ABSTRACT FROM PUBLISHER]

The low-rank approximation method is one of the most effective approaches recently proposed for attenuating random noise in seismic data. However, the low-rank approximation approach assumes that the seismic data has low rank for its $f-x$ domain Hankel matrix. This assumption is seldom satisfied for the complicated seismic data. Besides, the low-rank approximation approach is usually implemented in local windows in order to satisfy the principal assumption required by the algorithm itself. When implemented in local windows, the rank is even more difficult to choose because the seismic data is highly nonstationary in both time and spatial dimensions and the optimal rank for different local windows is not consistent with each other. In order to preserve enough useful energy, one needs to set a relatively large rank when implementing the low-rank approximation method, which makes the traditional method incapable of attenuating enough noise. Considering such difficulties described above, we propose an empirical low-rank approximation approach. We adaptively decompose the input data into several components that have truly low ranks via empirical mode decomposition. An interpretation of the proposed empirical low-rank approximation method is that we empirically decompose a multi-dip seismic image that is not of low rank into multiple single-dip seismic images that are low-rank individually. We use both synthetic and field data examples to demonstrate the superior performance of the proposed approach over traditional alternatives. [ABSTRACT FROM PUBLISHER]

Wireless sensor networks (WSNs) have been widely used in a plenty of applications. To achieve higher efficiency for data collection, WSNs are often partitioned into several disjointed clusters, each with a representative cluster head in charge of the data gathering and routing process. Such a partition is balanced and effective, if the distance between each node and its cluster head can be bounded within a constant number of hops, and any two cluster heads are connected. Finding such a cluster partition with minimum number of clusters and connectors between cluster heads is defined as minimum connected $d$ -hop dominating set ( d$ -MCDS) problem, which is proved to be NP-complete. In this paper, we propose a distributed approximation named CS-Cluster to address the d$ -MCDS problem under unit disk graph. CS-Cluster constructs a sparser d$ -hop maximal independent set ( d$ -MIS), connects the d$ -MIS, and finally checks and removes redundant nodes. We prove the approximation ratio of CS-Cluster is (2d+1)\lambda $ , where , our approximation ratio is a great improvement. Our evaluation results demonstrate the outstanding performance of our algorithm compared with previous works. [ABSTRACT FROM AUTHOR]

We consider a carrier sense multiple access (CSMA)-based scheduling algorithm for a single-hop wireless network under a realistic signal-to-interference-plus-noise ratio model for the interference. We propose two local optimization-based approximation algorithms to efficiently estimate certain attempt rate parameters of CSMA called fugacities. It is known that adaptive CSMA can achieve throughput optimality by sampling feasible schedules from a Gibbs distribution, with appropriate fugacities. Unfortunately, obtaining these optimal fugacities is an NP-hard problem. Furthermore, the existing adaptive CSMA algorithms use a stochastic gradient descent-based method, which usually entails an impractically slow (exponential in the size of the network) convergence to the optimal fugacities. To address this issue, we first propose an algorithm to estimate the fugacities, that can support a given set of desired service rates. The convergence rate and the complexity of this algorithm are independent of the network size, and depend only on the neighborhood size of a link. Furthermore, we show that the proposed algorithm corresponds exactly to performing the well-known Bethe approximation to the underlying Gibbs distribution. Then, we propose another local algorithm to estimate the optimal fugacities under a utility maximization framework, and characterize its accuracy. Numerical results indicate that the proposed methods have a good degree of accuracy, and achieve extremely fast convergence to near-optimal fugacities, and often outperform the convergence rate of the stochastic gradient descent by a few orders of magnitude. [ABSTRACT FROM AUTHOR]

In this study, to substantially improve the runtimes of exact and approximate string matching algorithms, we propose a tribrid parallel method for bit-parallel algorithms such as the Shift-Or and Wu-Manber algorithms. Our underlying idea is to interpret bit-parallel algorithms as inclusive-scan operations, which allow these bit-parallel algorithms to run efficiently on a graphics processing unit (GPU); we achieve this speed-up here because inclusive-scan operations not only eliminate duplicate searches between threads but also realize a GPU-friendly memory access pattern that maximizes memory read/write throughput. To realize our ideas, we first define two binary operators and then present a proof regarding the associativity of these operators, which is necessary for the parallelization of the inclusive-scan operations. Finally, we integrate the inclusive-scan scheme into a previous segmentation-based scheme to maximize search throughput, identifying the best tradeoff point between synchronization cost and duplicate work. Through our experiments, we compared our proposed method with previous segmentation-based methods and indexing-based sequence aligners. For online string matching, our proposed method performed 6.7-16.7 times faster than previous methods, achieving a search throughput of up to 1.88 terabits per second (Tbps) on a GeForce GTX TITAN X GPU. We therefore conclude that our proposed method is quite effective for decreasing the runtimes of online string matching of short patterns. [ABSTRACT FROM PUBLISHER]

A suboptimal algorithm to fixed-interval and fixed-lag smoothing for Markovian switching systems is proposed. It infers a Gaussian mixture approximation of the smoothing pdf by combining the statistics produced by an IMM filter into an original backward recursive process. The number of filters and smoothers is equal to the constant number of hypotheses in the posterior mixture. A comparison, conducted on simulated case studies, shows that the investigated method performs significantly better than equivalent algorithms. [ABSTRACT FROM PUBLISHER]

The reciprocal is a widespread operation in digital signal processing architectures. A usual method consists in using the Newton–Raphson algorithm or its derivatives, either in floating or in fixed-point formats. With the former format, the standardized format of the mantissa makes the implementation easier, but for the fixed-point format there are many possibilities. This forces a design with scaling of the input in order to respect a predetermined work range. Having the input in a known range makes it possible to compute a first approximation with coefficients stored in memory blocks. With this method, it is hard to propose a “ready to use” IP for all the fixed-point formats. In this letter, a novel architecture, which does not require scaling, is proposed. This design is totally pipelined, ROM-less and can be directly used in any architecture. The implementation was optimized to reach a maximum clock frequency of 740 MHz on a Virtex-7 Field-Programmable Gate Array (FPGA). [ABSTRACT FROM PUBLISHER]

Locality sensitive hashing (LSH) is an efficient method for solving the problem of approximate similarity search in high-dimensional spaces. Through LSH, a high-dimensional similarity join can be processed in the same way as hash join, making the cost of joining two large datasets linear. By judicially analyzing the properties of multiple LSH algorithms, we propose a generic method to speed up the process of joining two large datasets using LSH. The crux of our method lies in the way which we identify a set of representative points to reduce the number of LSH lookups. Theoretical analyzes show that our proposed method can greatly reduce the number of lookup operations and retain the same result accuracy compared to executing LSH lookups for every query point. Furthermore, we demonstrate the generality of our method by showing that the same principle can be applied to LSH algorithms for three different metrics: the Euclidean distance (QALSH), Jaccard similarity measure (MinHash), and Hamming distance (sequence hashing). Results from experimental studies using real datasets confirm our error analyzes and show significant improvements of our method over the state-of-the-art LSH method: to achieve over 0.95 recall, we only need to operate LSH lookups for at most 15 percent of the query points. [ABSTRACT FROM AUTHOR]

Small cells are introduced to cellular systems to enhance coverage and improve capacity. Densely deploying small cells can not only offload the traffic of macrocells but also provide an energy- and cost-efficient way to meet the sharp increase in traffic demands in mobile networks. However, such a cell deployment paradigm also leads to heterogeneous network (HetNet) infrastructure and raises new challenges for cell planning. In this paper, we study the cell planning issue in the HetNet. Our optimization task is to select a subset of candidate sites to deploy macro or small cells to minimize the total cost of ownership (TCO) or the energy consumption of the cellular system while satisfying practical constraints. We introduce approximation algorithms to cope with two different cell-planning cases, which are both NP-hard. First, we discuss the macrocell-only case. Our proposed algorithm achieves an approximation ratio of O(\log R) in this scenario, where R is the maximum achievable capacity of macrocells. Then, we introduce an O(\log \widetildeR)-approximation algorithm to the small-cell scenario, where \widetildeR is the maximum achievable capacity of a macrocell with small cells overlaid on it. Numerical results indicate that the HetNet can significantly reduce the TCO and the energy consumption of the cellular system. [ABSTRACT FROM PUBLISHER]

Total variation (TV) is a one of the most popular regularizers for stabilizing the solution of ill-posed inverse problems. This paper proposes a novel proximal-gradient algorithm for minimizing TV regularized least-squares cost functionals. Unlike traditional methods that require nested iterations for computing the proximal step of TV, our algorithm approximates the latter with several simple proximals that have closed form solutions. We theoretically prove that the proposed parallel proximal method achieves the TV solution with arbitrarily high precision at a global rate of converge that is equivalent to the fast proximal-gradient methods. The results in this paper have the potential to enhance the applicability of TV for solving very large-scale imaging inverse problems. [ABSTRACT FROM AUTHOR]

This paper introduces necessary and sufficient conditions that surrogate functions must satisfy to properly define frontiers of nondominated solutions in multiobjective optimization (MOO) problems. These new conditions work directly on the objective space, and thus are agnostic about how the solutions are evaluated. Therefore, real objectives or user-designed objectives’ surrogates are allowed, opening the possibility of linking independent objective surrogates. To illustrate the practical consequences of adopting the proposed conditions, we use Gaussian processes (GPs) as surrogates endowed with monotonicity soft constraints and with an adjustable degree of flexibility, and compare them to regular GPs and to a frontier surrogate method in the literature that is the closest to the method proposed in this paper. Results show that the necessary and sufficient conditions proposed here are finely managed by the constrained GP, guiding to high-quality surrogates capable of suitably synthesizing an approximation to the Pareto frontier in challenging instances of MOO, while an existing approach that does not take the theory proposed in consideration defines surrogates which greatly violate the conditions to describe a valid frontier. [ABSTRACT FROM PUBLISHER]

We consider the problem of reconstructing a low-rank matrix from a subset of its entries and analyze two variants of the so-called alternating minimization algorithm, which has been proposed in the past. We establish that when the underlying matrix has rank one, has positive bounded entries, and the graph underlying the revealed entries has diameter which is logarithmic in the size of the matrix, both algorithms succeed in reconstructing the matrix approximately in polynomial time starting from an arbitrary initialization. We further provide simulation results which suggest that the second variant which is based on the message passing type updates performs significantly better. [ABSTRACT FROM PUBLISHER]

The Booth multiplier has been widely used for high performance signed multiplication by encoding and thereby reducing the number of partial products. A multiplier using the radix-4 (or modified Booth) algorithm is very efficient due to the ease of partial product generation, whereas the radix-8 Booth multiplier is slow due to the complexity of generating the odd multiples of the multiplicand. In this paper, this issue is alleviated by the application of approximate designs. An approximate 2-bit adder is deliberately designed for calculating the sum of 1× and 2× of a binary number. This adder requires a small area, a low power and a short critical path delay. Subsequently, the 2-bit adder is employed to implement the less significant section of a recoding adder for generating the triple multiplicand with no carry propagation. In the pursuit of a trade-off between accuracy and power consumption, two signed 16 × 16 bit approximate radix-8 Booth multipliers are designed using the approximate recoding adder with and without the truncation of a number of less significant bits in the partial products. The proposed approximate multipliers are faster and more power efficient than the accurate Booth multiplier. The multiplier with 15-bit truncation achieves the best overall performance in terms of hardware and accuracy when compared to other approximate Booth multiplier designs. Finally, the approximate multipliers are applied to the design of a low-pass FIR filter and they show better performance than other approximate Booth multipliers. [ABSTRACT FROM AUTHOR]

Relay assignment significantly affects the performance of the cooperative communication, which is an emerging technology for the future mobile system. Previous studies in this area have mostly focused on assigning a dedicated relay to each source-destination pair for one-to-one (121) traffic. However, many-to-one (M21) traffic, which is also common in many situations (for example, several users associate with one access point in a wireless access network such as a WLAN), hasn't been well studied. This paper addresses the shared relay assignment (SRA) problem for M21 traffic. We formulate two new optimization problems: one is to maximize the minimum throughput among all the sources (hereafter called M21-SRA-MMT), and the other is to maximize the total throughput over all the sources while maintaining some degree of fairness (hereafter called M21-SRA-MTT). As the optimal solutions to the two problems are hard to find, we propose two approximation algorithms whose performance factors are 5.828 and 3, respectively, based on the rounding mechanism. Extensive simulation results show that our algorithms for M21-SRA-MMT can significantly improve the minimum throughput compared with existing algorithms, while our algorithm for M21-SRA-MTT can achieve the close-to-optimal performance. [ABSTRACT FROM AUTHOR]

The ever increasing demand for content is straining operators’ networks, thereby necessitating development of alternative content delivery mechanisms. Distributed caching architectures constitute a promising solution for mitigating the effects of demand growth by placing popular content files in proximity to users, rather than in a central site. In this paper, we study the content placement problem in multiple-level hierarchical caching networks where user requests for files are routed upwards toward content servers, satisfied by intermediate nodes if the latter have cached the requested files. Our goal is to reduce the server load by serving as many requests as possible by the caches. We show that the problem is NP-Hard in its general form, but it can be solved optimally in polynomial-time when the caches are installed on a single hierarchy path. For the general case, we develop an algorithm achieving a provably better approximation ratio than the best-known counterparts. Numerical experiments show up to 56% reduction in server load over existing algorithms, with gains increasing as the content popularity distributions get steeper and more diverse across nodes, and the cache capacities at the upper hierarchy levels increase. Our evaluation code is publicly available for the benefit of research community. [ABSTRACT FROM PUBLISHER]

This paper discusses Krylov subspace methods to solve a linear system whose coefficient matrix is represented by a hierarchical matrix. We propose a preconditioning technique using a part of the original hierarchical matrix to accelerate the convergence of the Krylov subspace methods. The proposed preconditioning technique is based on the assumption that the submatrices on the original hierarchical matrix are approximated using the adaptive cross approximation or variants thereof. The performance of Krylov subspace methods with the proposed preconditioning technique is examined through numerical experiments on an electrostatic field analysis. [ABSTRACT FROM AUTHOR]

We present an algorithm, along with its implementation that finds T-optimal approximations of single-qubit Z-rotations using quantum circuits consisting of Clifford and T gates. Our algorithm is capable of handling errors in approximation down to size 10^-15 , resulting in the optimal single-qubit circuit designs required for implementation of scalable quantum algorithms. Our implementation along with the experimental results are available in the public domain. [ABSTRACT FROM AUTHOR]

Visually analyzing citation networks poses challenges to many fields of the data mining research. How can we summarize a large citation graph according to the user’s interest? In particular, how can we illustrate the impact of a highly influential paper through the summarization? Can we maintain the sensory node-link graph structure while revealing the flow-based influence patterns and preserving a fine readability? The state-of-the-art influence maximization algorithms can detect the most influential node in a citation network, but fail to summarize a graph structure to account for its influence. On the other hand, existing graph summarization methods fold large graphs into clustered views, but can not reveal the hidden influence patterns underneath the citation network. In this paper, we first formally define the Influence Graph Summarization problem on citation networks. Second, we propose a matrix decomposition based algorithm pipeline to solve the IGS problem. Our method can not only highlight the flow-based influence patterns, but also easily extend to support the rich attribute information. A prototype system called VEGAS implementing this pipeline is also developed. Third, we present a theoretical analysis on our main algorithm, which is equivalent to the kernel k-mean clustering. It can be proved that the matrix decomposition based algorithm can approximate the objective of the proposed IGS problem. Last, we conduct comprehensive experiments with real-world citation networks to compare the proposed algorithm with classical graph summarization methods. Evaluation results demonstrate that our method significantly outperforms the previous ones in optimizing both the quantitative IGS objective and the quality of the visual summarizations. [ABSTRACT FROM PUBLISHER]

In this paper, we present a new methodology for a nonoverlapping domain decomposition method using boundary integral equations and adaptive cross approximation in the frequency domain (IE-ACA-DDM). This paper proposes two main novelties. First, the IE-DDM condition number is improved with the development of a formulation based on electric field integral equation (EFIE) implementation over the entire subdomains and on a simplification of the magnetic field integral equation (MFIE) on the interfaces. As a consequence, the number of matrix–vector products is significantly reduced during the iterative resolution. Then, this paper proves that the ACA can be applied and efficiently implemented in IE-DDM methods. Moreover, a hierarchical LU (HLU) decomposition is proposed to accelerate the ACA solver. The IE-ACA-DDM is very suitable for the resolution of multiple excitations and to bypass the low-frequency breakdown. The flexibility, accuracy, and efficiency of IE-ACA-DDM are demonstrated by comparing with reference integral equation solutions and scaled mock-up measurements. [ABSTRACT FROM PUBLISHER]

A fast and stable algorithm for approximation of sine and cosine hyperbolic functions is presented in this paper. The algorithm can be used for S-parameter calculation from RLGC parameters. The idea is to construct the recurrent relation for the approximate solution of sine and cosine hyperbolic complex value matrix functions. The stability of the proposed algorithm is shown and convergence theorem is proved. In the last section, different numerical simulations are made and compared with the already existing algorithm in terms of calculation time given. [ABSTRACT FROM AUTHOR]

Dynamic spectrum leasing (DSL) is a promising method to improve the spectrum efficiency. A lot of work has been done about spectrum sharing issues with static models. In this paper, we want to study the behavior of the primary users (PUs) under uncertainty. For this objective, we propose a model with time-varying parameters. The model captures both technical and economic features. We study the long-term behavior of the PUs in the model with stochastic Cournot game theory and variational inequality theory. We show that the PUs can maximize their long-term utilities with a static supply of spectrum. In addition, we also propose two algorithms based on stochastic approximation theory. The convergence and performance of the algorithms are demonstrated theoretically and numerically. The proposed model and analytical framework can be used to study and predict the behaviors of PUs given a DSL system and provide design insights for the DSL system. [ABSTRACT FROM AUTHOR]

In this letter, we propose HOG-Dot, a method for the direct computation of the polar image gradients coordinates from the pixels values. The proposed algorithm, to be used as the first step of the Histogram of Oriented Gradient (HOG) pipeline, approximates the exact gradient with its projection onto a versor chosen among the projection plane set. Instead of non linear computations, the HOG-Dot method exploits linear operations while introducing a bounded approximation error with respect to other HOG approaches, thus resulting a more suitable solution for embedded devices. Concerning the state of the art, it also achieves improved accuracy with the mathematical spatial gradient formulation . [ABSTRACT FROM PUBLISHER]

Matrix rank minimizing subject to affine constraints arises in many application areas, ranging from signal processing to machine learning. Nuclear norm is a convex relaxation for this problem which can recover the rank exactly under some restricted and theoretically interesting conditions. However, for many real-world applications, nuclear norm approximation to the rank function can only produce a result far from the optimum. To seek a solution of higher accuracy than the nuclear norm, in this letter, we propose a rank approximation based on Logarithm-Determinant. We consider using this rank approximation for subspace clustering application. Our framework can model different kinds of errors and noise. Effective optimization strategy is developed with theoretical guarantee to converge to a stationary point. The proposed method gives promising results on face clustering and motion segmentation tasks compared to the state-of-the-art subspace clustering algorithms. [ABSTRACT FROM PUBLISHER]

A new strategy for multiple structured dictionary learning is proposed. It is motivated by the fact that a signal and its residual after sparse approximation do not necessarily possess the same geometric structure. Based on the geometric structure of each residual component, the most appropriate dictionary is selected. A single-atom sparse representation vector of this residual is calculated and the chosen dictionary is updated. For a given training signal, the process of model (dictionary) selection and one-atom representation is repeated until the desired sparsity or approximation error is reached. Thus, the proposed strategy provides a mechanism whereby each signal can update the most relevant dictionaries based on the structure of its residuals. Simulations conducted over natural images show that, in comparison to standard single or multiple dictionary learning and sparse representation approaches, the proposed strategy significantly improves the representation quality. [ABSTRACT FROM PUBLISHER]