Search

We study the topic of dimensionality reduction for $k$ -means clustering. Dimensionality reduction encompasses the union of two approaches: 1) feature selection and 2) feature extraction. A feature selection-based algorithm for $k$ -means clustering selects a small subset of the input features and then applies $k$ -means clustering on the selected features. A feature extraction-based algorithm for $k$ -means clustering constructs a small set of new artificial features and then applies $k$ -means clustering on the constructed features. Despite the significance of $k$ -means clustering as well as the wealth of heuristic methods addressing it, provably accurate feature selection methods for $k$ -means clustering are not known. On the other hand, two provably accurate feature extraction methods for $k$ -means clustering are known in the literature; one is based on random projections and the other is based on the singular value decomposition (SVD). This paper makes further progress toward a better understanding of dimensionality reduction for $k$ -means clustering. Namely, we present the first provably accurate feature selection method for $k$ -means clustering and, in addition, we present two feature extraction methods. The first feature extraction method is based on random projections and it improves upon the existing results in terms of time complexity and number of features needed to be extracted. The second feature extraction method is based on fast approximate SVD factorizations and it also improves upon the existing results in terms of time complexity. The proposed algorithms are randomized and provide constant-factor approximation guarantees with respect to the optimal $k$ -means objective value. [ABSTRACT FROM AUTHOR]

Random projection has been widely used in data classification. It maps high-dimensional data into a low-dimensional subspace in order to reduce the computational cost in solving the related optimization problem. While previous studies are focused on analyzing the classification performance in the low-dimensional space, in this paper, we consider the recovery problem, i.e., how to accurately recover the optimal solution to the original high-dimensional optimization problem based on the solution learned after random projection. We present a simple algorithm, termed dual random projection, which uses the dual solution of the low-dimensional optimization problem to recover the optimal solution to the original problem. Our theoretical analysis shows that with a high probability, the proposed algorithm is able to accurately recover the optimal solution to the original problem, provided that the data matrix is (approximately) low-rank and/or optimal solution is (approximately) sparse. We further show that the proposed algorithm can be applied iteratively to reducing the recovery error exponentially. [ABSTRACT FROM PUBLISHER]

Compressed sensing is a technique for finding sparse solutions to underdetermined linear systems. This technique relies on properties of the sensing matrix such as the restricted isometry property. Sensing matrices that satisfy this property with optimal parameters are mainly obtained via probabilistic arguments. Deciding whether a given matrix satisfies the restricted isometry property is a nontrivial computational problem. Indeed, it is shown in this paper that restricted isometry parameters cannot be approximated in polynomial time within any constant factor under the assumption that the hidden clique problem is hard. In addition, on the positive side, an improvement on the brute-force enumeration algorithm for checking the restricted isometry property is proposed. [ABSTRACT FROM PUBLISHER]

An approximation of maximum-likelihood decoding over the binary symmetric channel was introduced by Omura in 1972. This decoder employs an iterative, randomized algorithm whose behavior closely mimics that of the simplex algorithm. In this paper, we generalize Omura's decoder to operate on an arbitrary binary-input memoryless channel. Further, we prove that the probability of the generalized Omura decoder (and hence Omura's original decoder) returning a maximum-likelihood codeword approaches 1 as the number of iterations goes to infinity, a result that has hereto remained unproven. [ABSTRACT FROM PUBLISHER]

We consider the estimation of an independent and identically distributed (i.i.d.) (possibly non-Gaussian) vector \bf x\in\BBR^n from measurements \bf y\in\BBR^m obtained by a general cascade model consisting of a known linear transform followed by a probabilistic componentwise (possibly nonlinear) measurement channel. A novel method, called adaptive generalized approximate message passing (adaptive GAMP) is presented. It enables the joint learning of the statistics of the prior and measurement channel along with estimation of the unknown vector \bf x . We prove that, for large i.i.d. Gaussian transform matrices, the asymptotic componentwise behavior of the adaptive GAMP is predicted by a simple set of scalar state evolution equations. In addition, we show that the adaptive GAMP yields asymptotically consistent parameter estimates, when a certain maximum-likelihood estimation can be performed in each step. This implies that the algorithm achieves a reconstruction quality equivalent to the oracle algorithm that knows the correct parameter values. Remarkably, this result applies to essentially arbitrary parametrizations of the unknown distributions, including nonlinear and non-Gaussian ones. The adaptive GAMP methodology thus provides a systematic, general and computationally efficient method applicable to a large range of linear–nonlinear models with provable guarantees. [ABSTRACT FROM AUTHOR]

Compressive sensing (CS) has recently emerged as a powerful framework for acquiring sparse signals. The bulk of the CS literature has focused on the case where the acquired signal has a sparse or compressible representation in an orthonormal basis. In practice, however, there are many signals that cannot be sparsely represented or approximated using an orthonormal basis, but that do have sparse representations in a redundant dictionary. Standard results in CS can sometimes be extended to handle this case provided that the dictionary is sufficiently incoherent or well conditioned, but these approaches fail to address the case of a truly redundant or overcomplete dictionary. In this paper, we describe a variant of the iterative recovery algorithm CoSaMP for this more challenging setting. We utilize the \mbi D-RIP, a condition on the sensing matrix analogous to the well-known restricted isometry property. In contrast to prior work, the method and analysis are “signal-focused”; that is, they are oriented around recovering the signal rather than its dictionary coefficients. Under the assumption that we have a near-optimal scheme for projecting vectors in signal space onto the model family of candidate sparse signals, we provide provable recovery guarantees. Developing a practical algorithm that can provably compute the required near-optimal projections remains a significant open problem, but we include simulation results using various heuristics that empirically exhibit superior performance to traditional recovery algorithms. [ABSTRACT FROM AUTHOR]

We study the (constrained) least-squares regression as well as multiple response least-squares regression and ask the question of whether a subset of the data, a coreset, suffices to compute a good approximate solution to the regression. We give deterministic, low-order polynomial-time algorithms to construct such coresets with approximation guarantees, together with lower bounds indicating that there is not much room for improvement upon our results. [ABSTRACT FROM AUTHOR]

Index coding has received considerable attention recently motivated in part by applications such as fast video-on-demand and efficient communication in wireless networks and in part by its connection to network coding. Optimal encoding schemes and efficient heuristics were studied in various settings, while also leading to new results for network coding such as improved gaps between linear and non-linear capacity as well as hardness of approximation. The problem of broadcasting with side information, a generalization of the index coding problem, begins with a sender and sets of users and messages. Each user possesses a subset of the messages and desires an additional message from the set. The sender wishes to broadcast a message so that on receipt of the broadcast each user can compute her desired message. The fundamental parameter of interest is the broadcast rate, \beta , the average communication cost for sufficiently long broadcasts. Though there have been many new nontrivial bounds on \beta by Bar-Yossef (2006), Lubetzky and Stav (2007), Alon (2008), and Blasiak (2011) there was no known polynomial-time algorithm for approximating \beta within a nontrivial factor, and the exact value of \beta remained unknown for all nontrivial instances. Using the information theoretic linear program introduced in Blasiak (2011), we give a polynomial-time algorithm for recognizing instances with \beta = 2 and pinpoint \beta precisely for various classes of graphs (e.g., various Cayley graphs of cyclic groups). Further, extending ideas from Ramsey theory, we give a polynomial-time algorithm with a nontrivial approximation ratio for computing \beta . Finally, we provide insight into the quality of previous bounds by giving constructions showing separations between \beta and the respective bounds. In particular, we construct graphs where \beta is uniformly bounded while its upper bound derived from the naïve encoding scheme is polynomially worse. [ABSTRACT FROM AUTHOR]

Compressed sensing posits that, within limits, one can undersample a sparse signal and yet reconstruct it accurately. Knowing the precise limits to such undersampling is important both for theory and practice. We present a formula that characterizes the allowed undersampling of generalized sparse objects. The formula applies to approximate message passing (AMP) algorithms for compressed sensing, which are here generalized to employ denoising operators besides the traditional scalar soft thresholding denoiser. This paper gives several examples including scalar denoisers not derived from convex penalization—the firm shrinkage nonlinearity and the minimax nonlinearity—and also nonscalar denoisers—block thresholding, monotone regression, and total variation minimization. Let the variables \varepsilon = k/N and \delta = n/N denote the generalized sparsity and undersampling fractions for sampling the k-generalized-sparse N-vector x0 according to y=Ax0. Here, A is an n\times N measurement matrix whose entries are iid standard Gaussian. The formula states that the phase transition curve \delta = \delta (\varepsilon ) separating successful from unsuccessful reconstruction of x0 by AMP is given by \delta = M(\varepsilon \vert Denoiser) where M(\varepsilon \vert Denoiser) denotes the per-coordinate minimax mean squared error (MSE) of the specified, optimally tuned denoiser in the directly observed problem y = x + z. In short, the phase transition of a noiseless undersampling problem is identical to the minimax MSE in a denoising problem. We prove that this formula follows from state evolution and present numerical results validating it in a wide range of settings. The above formula generates numerous new insights, both in the scalar and in the nonscalar cases. [ABSTRACT FROM PUBLISHER]

The closest vector problem (CVP) and shortest (nonzero) vector problem (SVP) are the core algorithmic problems on Euclidean lattices. They are central to the applications of lattices in many problems of communications and cryptography. Kannan's embedding technique is a powerful technique for solving the approximate CVP; yet, its remarkable practical performance is not well understood. In this paper, the embedding technique is analyzed from a bounded distance decoding (BDD) viewpoint. We present two complementary analyses of the embedding technique: we establish a reduction from BDD to Hermite SVP (via unique SVP), which can be used along with any Hermite SVP solver (including, among others, the Lenstra, Lenstra and Lovász (LLL) algorithm), and show that, in the special case of LLL, it performs at least as well as Babai's nearest plane algorithm (LLL-aided successive interference cancellation). The former analysis helps us to explain the folklore practical observation that unique SVP is easier than standard approximate SVP. It is proven that when the LLL algorithm is employed, the embedding technique can solve the CVP provided that the noise norm is smaller than a decoding radius \lambda1/(2\gamma), where \lambda1 is the minimum distance of the lattice, and \gamma\approx O(2^n/4). This substantially improves the previously best known correct decoding bound \gamma\approxO(2^n). Focusing on the applications of BDD to decoding of multiple-input multiple-output systems, we also prove that BDD of the regularized lattice is optimal in terms of the diversity–multiplexing gain tradeoff, and propose practical variants of embedding decoding which require no knowledge of the minimum distance of the lattice and/or further improve the error performance. [ABSTRACT FROM PUBLISHER]

It has recently been observed that the permanent of a nonnegative square matrix, i.e., of a square matrix containing only nonnegative real entries, can very well be approximated by solving a certain Bethe free energy function minimization problem with the help of the sum–product algorithm. We call the resulting approximation of the permanent the Bethe permanent. In this paper, we give reasons why this approach to approximating the permanent works well. Namely, we show that the Bethe free energy function is convex and that the sum–product algorithm finds its minimum efficiently. We then discuss the fact that the permanent is lower bounded by the Bethe permanent, and we comment on potential upper bounds on the permanent based on the Bethe permanent. We also present a combinatorial characterization of the Bethe permanent in terms of permanents of so-called lifted versions of the matrix under consideration. Moreover, we comment on possibilities to modify the Bethe permanent so that it approximates the permanent even better, and we conclude the paper with some observations and conjectures about permanent-based pseudocodewords and permanent-based kernels. [ABSTRACT FROM AUTHOR]

Suppose that we observe noisy linear measurements of an unknown signal that can be modeled as the sum of two component signals, each of which arises from a nonlinear submanifold of a high-dimensional ambient space. We introduce successive projections onto incoherent manifolds (SPIN), a first-order projected gradient method to recover the signal components. Despite the nonconvex nature of the recovery problem and the possibility of underdetermined measurements, SPIN provably recovers the signal components, provided that the signal manifolds are incoherent and that the measurement operator satisfies a certain restricted isometry property. SPIN significantly extends the scope of current recovery models and algorithms for low-dimensional linear inverse problems and matches (or exceeds) the current state of the art in terms of performance. [ABSTRACT FROM AUTHOR]

Determining the minimum distance of a linear code is one of the most important problems in algorithmic coding theory. The exact version of the problem was shown to be NP-complete by Vardy. The gap version of the problem was shown to be NP-hard for any constant factor under a randomized reduction in an earlier work. It was shown in the same paper that the minimum distance problem is not approximable in randomized polynomial time to the factor 2^\log^1-\epsilonn unless NP\subseteq RTIME(2^polylog(n)). In this paper, we derandomize the reduction and thus prove that there is no deterministic polynomial time algorithm to approximate the minimum distance to any constant factor unless P=NP. We also prove that the minimum distance is not approximable in deterministic polynomial time to the factor 2^\log^1-\epsilonn unless NP\subseteq DTIME(2^polylog(n)). As the main technical contribution, for any constant 2/3 < \rho < 1, we present a deterministic algorithm that given a positive integer s, runs in time poly(s) and constructs a code \cal C of length poly(s) with an explicit Hamming ball of radius \rho d(\cal C), such that the projection at the first s coordinates sends the codewords in the ball surjectively onto a linear subspace of dimension s, where d(\cal C) denotes the minimum distance of \cal C. The codes are obtained by concatenating Reed–Solomon codes with Hadamard codes. [ABSTRACT FROM PUBLISHER]

We study the effect on diversity of using the sphere encoder-based vector perturbation (VP) technique of Peel and the lattice reduction-aided techniques (Babai approximations) of Windpassinger on a subset of the transmitted symbols. For a system with n diversity channels, we prove that the diversity order gap between the maximum diversity of n achieved by the full-size VP and the minimum diversity of 1 provided by linear precoding can be bridged by applying VP to a group of transmitted symbols. In particular, we prove that the diversity order is n-l, where l is the number of symbols that are not vector-perturbed. We show that this result holds true for lattice-reduction with both the rounding-off and nearest plane Babai approximations. The result shows that in terms of diversity, the group of vector-perturbed users counts as a single user. In fact, in a multiple-input and multiple-output Gaussian broadcast channel with l linearly precoded users, we can add up to n-l VP users and the diversity order for all users will decrease only by one, irrespective of how many VP users are added. [ABSTRACT FROM PUBLISHER]

We consider the problem of finding high-dimensional approximate nearest neighbors. We introduce an old style probabilistic formulation instead of the more general locality sensitive hashing (LSH) formulation, and show that at least for sparse problems it recognizes much more efficient algorithms than the sparseness destroying LSH random projections. Efficient algorithms for homogeneous (all coordinates have the same probability distribution) problems are well known, the most famous reference being the work by Broder in 1998. The main theme of this paper is to find its “best” generalization to heterogeneous (different coordinate probabilities) problems. We find a practical algorithm which is asymptotically best in a wide natural class of algorithms. Readers interested in the more complicated very best (at least up to date) can look up our previous work in 2010. The analysis of our algorithms reveals that its complexity is governed by an information like function, which we call “small leaves bucketing forest information.” Any doubts whether it is “information” are dispelled by the aforementioned work. [ABSTRACT FROM PUBLISHER]

We formulate and solve the problem of optimal channel coding and flow-rate control for serving deadline-constrained traffic with average delivery ratio requirements (typical of multimedia streaming and interactive real-time applications) over time-varying channels. To that end, we first characterize the largest set of arrival processes (rather than rates) whose deadline and delivery ratio requirements can be satisfied. Then, we propose a dynamic (channel) coding algorithm that provably satisfies the requirements of any arrival process in this region. This optimal dynamic algorithm evolves through simple iterations to utilize a combination of pricing and finite-horizon dynamic programming operations. Next, we proposed two low-complexity approximations of the algorithm that has provable performance. We also extend the setup to allow for a flow controller that adjusts the incoming flow rates to satisfy their delivery ratio constraints when the arrival process is unknown but controllable. We propose a joint dynamic coding and a rate control algorithm to solve this problem, and prove its stability under the stochastic system operation. We also apply these general results to an important wireless down-link broadcast scenario with and without random network coding capabilities. Our theoretical work is supported by extensive numerical studies, which also reveal that our dynamic coding strategy outperforms any static coding strategy by opportunistically exploiting the statistical variations in the arrival and channel processes. [ABSTRACT FROM PUBLISHER]

We consider codes over permutations under the infinity norm. Given such a code, we show that a simple relabeling operation, which produces an isomorphic code, may drastically change the minimal distance of the code. Thus, we may choose a code structure for efficient encoding procedures, and then optimize the code's minimal distance via relabeling. To establish that the relabeling problem is hard and is of interest, we formally define it and show that all codes may be relabeled to get a minimal distance at most 2. On the other hand, the decision problem of whether a code may be relabeled to distance 2 or more is shown to be NP-complete, and calculating the best achievable minimal distance after relabeling is proved to be hard to approximate up to a factor of 2. We then consider general bounds on the relabeling problem. We specifically construct the optimal relabeling for transitive cyclic groups. We conclude with the main result—a general probabilistic bound, which we then use to show both the \mathopAGL(p) group and the dihedral group on p elements may be relabeled to a minimal distance of p-O(\sqrtp\ln p). [ABSTRACT FROM PUBLISHER]

We present a new lossy compressor for finite-alphabet sources. For coding a sequence x^n, the encoder starts by assigning a certain cost to each possible reconstruction sequence. It then finds the one that minimizes this cost and describes it losslessly to the decoder via a universal lossless compressor. The cost of each sequence is a linear combination of its distance from the sequence x^n and a linear function of its k^th order empirical distribution. The structure of the cost function allows the encoder to employ the Viterbi algorithm to find the sequence with minimum cost. We identify a choice of the coefficients used in the cost function which ensures that the algorithm universally achieves the optimum rate-distortion performance for any stationary ergodic source, in the limit of large n, provided that k increases as o(\log n). Iterative techniques for approximating the coefficients, which alleviate the computational burden of finding the optimal coefficients, are proposed and studied. [ABSTRACT FROM AUTHOR]

The general theory of greedy approximation is well developed. Much less is known about how specific features of a dictionary can be used to our advantage. In this paper, we discuss incoherent dictionaries. We build a new greedy algorithm which is called the orthogonal super greedy algorithm (OSGA). We show that the rates of convergence of OSGA and the orthogonal matching pursuit (OMP) with respect to incoherent dictionaries are the same. Based on the analysis of the number of orthogonal projections and the number of iterations, we observed that OSGA(s) is s times simpler (more efficient) than OMP. Greedy approximation is also a fundamental tool for sparse signal recovery. The performance of orthogonal multimatching pursuit, a counterpart of OSGA in the compressed sensing setting, is also analyzed under restricted isometry property conditions. [ABSTRACT FROM AUTHOR]