The Round Complexity of Small Set Intersection
David P. Woodruff, Grigory Yaroslavtsev
(Submitted on 5 Apr 2013)
The set disjointness problem is one of the most fundamental and well-studied problems in communication complexity. In this problem Alice and Bob hold sets $S, T \subseteq [n]$, respectively, and the goal is to decide if $S \cap T = \emptyset$. Reductions from set disjointness are a canonical way of proving lower bounds in data stream algorithms, data structures, and distributed computation. In these applications, often the set sizes $|S|$ and $|T|$ are bounded by a value $k$ which is much smaller than $n$. This is referred to as small set disjointness. A major restriction in the above applications is the number of rounds that the protocol can make, which, e.g., translates to the number of passes in streaming applications. A fundamental question is thus in understanding the round complexity of the small set disjointness problem. For an essentially equivalent problem, called OR-Equality, Brody et. al showed that with $r$ rounds of communication, the randomized communication complexity is $\Omega(k \ilog^r k)$, where$\ilog^r k$ denotes the $r$-th iterated logarithm function. Unfortunately their result requires the error probability of the protocol to be $1/k^{\Theta(1)}$. Since na\"ive amplification of the success probability of a protocol from constant to $1-1/k^{\Theta(1)}$ blows up the communication by a $\Theta(\log k)$ factor, this destroys their improvements over the well-known lower bound of $\Omega(k)$ which holds for any number of rounds. They pose it as an open question to achieve the same $\Omega(k \ilog^r k)$ lower bound for protocols with constant error probability. We answer this open question by showing that the $r$-round randomized communication complexity of ${\sf OREQ}_{n,k}$, and thus also of small set disjointness, with {\it constant error probability} is $\Omega(k \ilog^r k)$, asymptotically matching known upper bounds for ${\sf OREQ}_{n,k}$ and small set disjointness.
The H-band Emitting Region of the Luminous Blue Variable P Cygni: Spectrophotometry and Interferometry of the Wind
N. D. Richardson, G. H. Schaefer, D. R. Gies, O. Chesneau, J. D. Monnier,F. Baron, X. Che, J. R. Parks, R. A. Matson, Y. Touhami, D. P. Clemens,E. J. Aldoretta, N. D. Morrison, T. A. ten Brummelaar, H. A. McAlister, S. Kraus, S. T. Ridgway, J. Sturmann, L. Sturmann, B. Taylor, N. H. Turner,C. D. Farrington, P. J. Goldfinger
(Submitted on 4 Apr 2013)
We present the first high angular resolution observations in the nearinfrared H-band (1.6 microns) of the Luminous Blue Variable star P Cygni. We obtained six-telescope interferometric observations with the CHARA Array and the MIRC beam combiner. These show that the spatial flux distribution is larger than expected for the stellar photosphere. A two component model for the star (uniform disk) plus a halo (two-dimensional Gaussian) yields an excellent fit of the observations, and we suggest that the halo corresponds to flux emitted from the base of the stellar wind. This wind component contributes about 45% of the H-band flux and has an angular FWHM = 0.96 mas, compared to the predicted stellar diameter of 0.41 mas. We show several images reconstructed from the interferometric visibilities and closure phases, and they indicate a generally spherical geometry for the wind. We also obtained near-infrared spectrophotometry of P Cygni from which we derive the flux excess compared to a purely photospheric spectral energy distribution. The H-band flux excess matches that from the wind flux fraction derived from the two component fits to the interferometry. We find evidence of significant near-infrared flux variability over the period from 2006 to 2010 that appears similar to the variations in the H-alpha emission flux from the wind. Future interferometric observations may be capable of recording the spatial variations associated with temporal changes in the wind structure.
Regularly random duality
Mihailo Stojnic
(Submitted on 29 Mar 2013)
In this paper we look at a class of random optimization problems. We discuss ways that can help determine typical behavior of their solutions. When the dimensions of the optimization problems are large such an information often can be obtained without actually solving the original problems. Moreover, we also discover that fairly often one can actually determine many quantities of interest (such as, for example, the typical optimal values of the objective functions) completely analytically. We present a few general ideas and emphasize that the range of applications is enormous.
A framework to characterize performance of LASSO algorithms
Mihailo Stojnic
(Submitted on 29 Mar 2013)
In this paper we consider solving \emph{noisy} under-determined systems of linear equations with sparse solutions. A noiseless equivalent attracted enormous attention in recent years, above all, due to work of \cite{CRT,CanRomTao06,DonohoPol} where it was shown in a statistical and large dimensional context that a sparse unknown vector (of sparsity proportional to the length of the vector) can be recovered from an under-determined system via a simple polynomial $\ell_1$-optimization algorithm. \cite{CanRomTao06} further established that even when the equations are \emph{noisy}, one can, through an SOCP noisy equivalent of $\ell_1$, obtain an approximate solution that is (in an $\ell_2$-norm sense) no further than a constant times the noise from the sparse unknown vector. In our recent works \cite{StojnicCSetam09,StojnicUpper10}, we created a powerful mechanism that helped us characterize exactly the performance of $\ell_1$ optimization in the noiseless case (as shown in \cite{StojnicEquiv10} and as it must be if the axioms of mathematics are well set, the results of \cite{StojnicCSetam09,StojnicUpper10} are in an absolute agreement with the corresponding exact ones from \cite{DonohoPol}). In this paper we design a mechanism, as powerful as those from \cite{StojnicCSetam09,StojnicUpper10}, that can handle the analysis of a LASSO type of algorithm (and many others) that can be (or typically are) used for "solving" noisy under-determined systems. Using the mechanism we then, in a statistical context, compute the exact worst-case $\ell_2$ norm distance between the unknown sparse vector and the approximate one obtained through such a LASSO. The obtained results match the corresponding exact ones obtained in \cite{BayMon10,DonMalMon10}. Moreover, as a by-product of our analysis framework we recognize existence of an SOCP type of algorithm that achieves the same performance.
Upper-bounding $\ell_1$-optimization weak thresholds
Mihailo Stojnic
(Submitted on 29 Mar 2013)
In our recent work \cite{StojnicCSetam09} we considered solving under-determined systems of linear equations with sparse solutions. In a large dimensional and statistical context we proved that if the number of equations in the system is proportional to the length of the unknown vector then there is a sparsity (number of non-zero elements of the unknown vector) also proportional to the length of the unknown vector such that a polynomial $\ell_1$-optimization technique succeeds in solving the system. We provided lower bounds on the proportionality constants that are in a solid numerical agreement with what one can observe through numerical experiments. Here we create a mechanism that can be used to derive the upper bounds on the proportionality constants. Moreover, the upper bounds obtained through such a mechanism match the lower bounds from \cite{StojnicCSetam09} and ultimately make the latter ones optimal.
A rigorous geometry-probability equivalence in characterization of $\ell_1$-optimization
Mihailo Stojnic
(Submitted on 29 Mar 2013)
In this paper we consider under-determined systems of linear equations that have sparse solutions. This subject attracted enormous amount of interest in recent years primarily due to influential works \cite{CRT,DonohoPol}. In a statistical context it was rigorously established for the first time in \cite{CRT,DonohoPol} that if the number of equations is smaller than but still linearly proportional to the number of unknowns then a sparse vector of sparsity also linearly proportional to the number of unknowns can be recovered through a polynomial $\ell_1$-optimization algorithm (of course, this assuming that such a sparse solution vector exists). Moreover, the geometric approach of \cite{DonohoPol} produced the exact values for the proportionalities in question. In our recent work \cite{StojnicCSetam09} we introduced an alternative statistical approach that produced attainable values of the proportionalities. Those happened to be in an excellent numerical agreement with the ones of \cite{DonohoPol}. In this paper we give a rigorous analytical confirmation that the results of \cite{StojnicCSetam09} indeed match those from \cite{DonohoPol}.
Convergence of a data-driven time-frequency analysis method
Thomas Y. Hou, Zuoqiang Shi, Peyman Tavallali
(Submitted on 28 Mar 2013)
In a recent paper, Hou and Shi introduced a new adaptive data analysis method to analyze nonlinear and non-stationary data. The main idea is to look for the sparsest representation of multiscale data within the largest possible dictionary consisting of intrinsic mode functions of the form $\{a(t) \cos(\theta(t))\}$, where $a \in V(\theta)$, $V(\theta)$ consists of the functions smoother than $\cos(\theta(t))$ and $\theta'\ge 0$. This problem was formulated as a nonlinear $L^0$ optimization problem and an iterative nonlinear matching pursuit method was proposed to solve this nonlinear optimization problem. In this paper, we prove the convergence of this nonlinear matching pursuit method under some sparsity assumption on the signal. We consider both well-resolved and sparse sampled signals. In the case without noise, we prove that our method gives exact recovery of the original signal.
Sparse approximation and recovery by greedy algorithms in Banach spaces
Vladimir Temlyakov
(Submitted on 27 Mar 2013)
We study sparse approximation by greedy algorithms. We prove the Lebesgue-type inequalities for the Weak Chebyshev Greedy Algorithm (WCGA), a generalization of the Weak Orthogonal Matching Pursuit to the case of a Banach space. The main novelty of these results is a Banach space setting instead of a Hilbert space setting. The results are proved for redundant dictionaries satisfying certain conditions. Then we apply these general results to the case of bases. In particular, we prove that the WCGA provides almost optimal sparse approximation for the trigonometric system in $L_p$, $2\le p<\infty$.
Sketching Sparse Matrices
Gautam Dasarathy, Parikshit Shah, Badri Narayan Bhaskar, Robert Nowak
(Submitted on 26 Mar 2013)
This paper considers the problem of recovering an unknown sparse p\times p matrix X from an m\times m matrix Y=AXB^T, where A and B are known m \times p matrices with m << p.
The main result shows that there exist constructions of the "sketching" matrices A and B so that even if X has O(p) non-zeros, it can be recovered exactly and efficiently using a convex program as long as these non-zeros are not concentrated in any single row/column of X. Furthermore, it suffices for the size of Y (the sketch dimension) to scale as m = O(\sqrt{# nonzeros in X} \times log p). The results also show that the recovery is robust and stable in the sense that if X is equal to a sparse matrix plus a perturbation, then the convex program we propose produces an approximation with accuracy proportional to the size of the perturbation. Unlike traditional results on sparse recovery, where the sensing matrix produces independent measurements, our sensing operator is highly constrained (it assumes a tensor product structure). Therefore, proving recovery guarantees require non-standard techniques. Indeed our approach relies on a novel result concerning tensor products of bipartite graphs, which may be of independent interest.
This problem is motivated by the following application, among others. Consider a p\times n data matrix D, consisting of n observations of p variables. Assume that the correlation matrix X:=DD^{T} is (approximately) sparse in the sense that each of the p variables is significantly correlated with only a few others. Our results show that these significant correlations can be detected even if we have access to only a sketch of the data S=AD with A \in R^{m\times p}.
Towards an information-theoretic system theory
Bernhard C. Geiger, Gernot Kubin
(Submitted on 26 Mar 2013)
In this work the information loss in deterministic, memoryless systems is investigated by evaluating the conditional entropy of the input random variable given the output random variable. It is shown that for a large class of systems the information loss is finite, even if the input is continuously distributed. Based on this finiteness, the problem of perfectly reconstructing the input is addressed and Fano-type bounds between the information loss and the reconstruction error probability are derived.
For systems with infinite information loss a relative measure is defined and shown to be tightly related to Renyi's information dimension. Employing another Fano-type argument, the reconstruction error probability is bounded by the relative information loss from below.
In view of developing a system theory from an information theoretic point-of-view, the theoretical results are illustrated at the hand of a few example systems, among them a multi-channel autocorrelation receiver.
Phase Transition Analysis of Sparse Support Detection from Noisy Measurements
Jaewook Kang, Heung-No Lee, Kiseon Kim
(Submitted on 26 Mar 2013 (v1), last revised 8 Apr 2013 (this version, v2))
This paper investigates the problem of sparse support detection (SSD) via a detection-oriented algorithm named Bayesian hypothesis test via belief propagation (BHT-BP). Our main focus is to compare BHT-BP to an estimation-based algorithm, called CS-BP, and show its superiority in the SSD problem. For this investigation, we perform a phase transition (PT) analysis over the plain of the noise level and signal magnitude on the signal support. This PT analysis sharply specifies the required signal magnitude for the detection under a certain noise level. In addition, we provide an experimental validation to assure the PT analysis. Our analytical and experimental results show the fact that BHT-BP detects the signal support against additive noise more robustly than CS-BP does.
Message Passing Algorithm for Distributed Downlink Regularized Zero-forcing Beamforming with Cooperative Base Stations
Chao-Kai Wen, Jung-Chieh Chen, Kai-Kit Wong, Pangan Ting
(Submitted on 26 Mar 2013)
Base station (BS) cooperation can turn unwanted interference to useful signal energy for enhancing system performance. In the cooperative downlink, zero-forcing beamforming (ZFBF) with a simple scheduler is well known to obtain nearly the performance of the capacity-achieving dirty-paper coding. However, the centralized ZFBF approach is prohibitively complex as the network size grows. In this paper, we devise message passing algorithms for realizing the regularized ZFBF (RZFBF) in a distributed manner using belief propagation. In the proposed methods, the overall computational cost is decomposed into many smaller computation tasks carried out by groups of neighboring BSs and communications is only required between neighboring BSs. More importantly, some exchanged messages can be computed based on channel statistics rather than instantaneous channel state information, leading to significant reduction in computational complexity. Simulation results demonstrate that the proposed algorithms converge quickly to the exact RZFBF and much faster compared to conventional methods.
Multi-Group Testing
Hong-Bin Chen, Fei-Huang Chang, Jun-Yi Guo, Yu-Pei Huang
(Submitted on 25 Mar 2013)
This paper proposes a novel generalization of group testing, called multi-group testing, which relaxes the notion of "testing subset" in group testing to "testing multi-set". The generalization aims to learn more information of each item to be tested rather than identify only defectives as was done in conventional group testing. This paper provides efficient nonadaptive strategies for the multi-group testing problem. The major tool is a new structure, $q$-ary additive $(w,d)$-disjunct matrix, which is a generalization of the well-known binary disjunct matrix introduced by Kautz and Singleton in 1964.
Circular law for random matrices with unconditional log-concave distribution
Radosław Adamczak, Djalil Chafai (LAMA)
(Submitted on 23 Mar 2013)
We explore the validity of the circular law for random matrices with non i.i.d. entries. Let A be a random n \times n real matrix having as a random vector in R^{n^2} a log-concave isotropic unconditional law. In particular, the entries are uncorellated and have a symmetric law of zero mean and unit variance. This allows for some dependence and non equidistribution among the entries, while keeping the special case of i.i.d. standard Gaussian entries. Our main result states that as n goes to infinity, the empirical spectral distribution of n^{-1/2}A tends to the uniform law on the unit disc of the complex plane.
Sparse Factor Analysis for Learning and Content Analytics
Andrew S. Lan, Andrew E. Waters, Christoph Studer, Richard G. Baraniuk
(Submitted on 22 Mar 2013)
We develop a new model and algorithms for machine learning-based learning analytics, which estimate a learner's knowledge of the concepts underlying a domain, and content analytics, which estimate the relationships among a collection of questions and those concepts. Our model represents the probability that a learner provides the correct response to a question in terms of three factors: their understanding of a set of underlying concepts, the concepts involved in each question, and each question's intrinsic difficulty. We estimate these factors given the graded responses to a collection of questions. The underlying estimation problem is ill-posed in general, especially when only a subset of the questions are answered. The key observation that enables a well-posed solution is the fact that typical educational domains of interest involve only a small number of key concepts. Leveraging this observation, we develop both a bi-convex maximum-likelihood and a Bayesian solution to the resulting SPARse Factor Analysis (SPARFA) problem. We also incorporate user-defined tags on questions to facilitate the interpretability of the estimated factors. Experiments with synthetic and real-world data demonstrate the efficacy of our approach. Finally, we make a connection between SPARFA and noisy, binary-valued (1-bit) dictionary learning that is of independent interest.
Can we allow linear dependencies in the dictionary in the sparse synthesis framework?
Raja Giryes, Michael Elad
(Submitted on 22 Mar 2013)
Signal recovery from a given set of linear measurements using a sparsity prior has been a major subject of research in recent years. In this model, the signal is assumed to have a sparse representation under a given dictionary. Most of the work dealing with this subject has focused on the reconstruction of the signal's representation as the means for recovering the signal itself. This approach forced the dictionary to be of low coherence and with no linear dependencies between its columns. Recently, a series of contributions that focus on signal recovery using the analysis model find that linear dependencies in the analysis dictionary are in fact permitted and beneficial. In this paper we show theoretically that the same holds also for signal recovery in the synthesis case for the l0- synthesis minimization problem. In addition, we demonstrate empirically the relevance of our conclusions for recovering the signal using an l1-relaxation.
Nonlocal imaging by conditional averaging of random reference measurements
Kai-Hong Luo, Boqiang Huang, Wei-Mou Zheng, Ling-An Wu
(Submitted on 22 Mar 2013)
We report the nonlocal imaging of an object by conditional averaging of the random exposure frames of a reference detector, which only sees the freely propagating field from a thermal light source. A bucket detector, synchronized with the reference detector, records the intensity fluctuations of an identical beam passing through the object mask. These fluctuations are sorted according to their values relative to the mean, then the reference data in the corresponding time-bins for a given fluctuation range are averaged, to produce either positive or negative images. Since no correlation calculations are involved, this correspondence imaging technique challenges our former interpretations of "ghost" imaging. Compared with conventional correlation imaging or compressed sensing schemes, both the number of exposures and computation time are greatly reduced, while the visibility is much improved. A simple statistical model is presented to explain the phenomenon.
Sample Distortion for Compressed Imaging
Chunli Guo, Mike E. Davies
(Submitted on 22 Mar 2013)
We propose the notion of sample distortion function for i.i.d compressive distributions with the aim to fundamentally quantify the achievable reconstruction performance of compressed sensing for certain encoder-decoder pairs at a given undersampling ratio. The theoretical SD function is derived for the Gaussian encoder and Bayesian optimal approximate message passing decoder thanks to the rigorous analysis of the AMP algorithm. We also show the convexity of the general SD function and derive two lower bounds. We then apply the SD framework to analyse compressed sensing for natural images using a multi-resolution statistical image model with both generalized Gaussian distribution and the two-state Gaussian mixture distribution. For this scenario we are able to achieve an optimal bandwise sample allocation and the corresponding SD function for natural images to accurately predict the possible compressed sensing performance gains. We further adopt Som and Schniter's turbo message passing approach to integrate the bandwise sampling with the exploitation of the hidden Markov tree structure of wavelet coefficients. Natural image simulation confirms the theoretical improvements and the effectiveness of bandwise sampling.
Projection Onto The k-Cosparse Set is NP-Hard
Andreas M. Tillmann, Rémi Gribonval, Marc E. Pfetsch
The computational complexity of a problem arising in the context of sparse optimization is considered, namely, the projection onto the set of k-cosparse vectors w.r.t. some given matrix {\Omega}. It is shown that this projection problem is (strongly) NP-hard, even in the special cases where the matrix {\Omega} contains only ternary or bipolar coefficients. Interestingly, this is in contrast to the projection onto the set of k-sparse vectors, which is trivially solved by keeping only the k largest coefficients.
Multi-dimensional sparse structured signal approximation using split Bregman iterations
Yoann Isaac, Quentin Barthélemy, Jamal Atif, Cédric Gouy-Pailler, Michèle Sebag
(Submitted on 21 Mar 2013 (v1), last revised 25 Mar 2013 (this version, v2))
The paper focuses on the sparse approximation of signals using overcomplete representations, such that it preserves the (prior) structure of multi-dimensional signals. The underlying optimization problem is tackled using a multi-dimensional split Bregman optimization approach. An extensive empirical evaluation shows how the proposed approach compares to the state of the art depending on the signal features.
On the optimality of a L1/L1 solver for sparse signal recovery from sparsely corrupted compressive measurements
Laurent Jacques
(Submitted on 20 Mar 2013)
This short note proves the $\ell_2-\ell_1$ instance optimality of a $\ell_1/\ell_1$ solver, i.e a variant of \emph{basis pursuit denoising} with a $\ell_1$ fidelity constraint, when applied to the estimation of sparse (or compressible) signals observed by sparsely corrupted compressive measurements. The approach simply combines two known results due to Y. Plan, R. Vershynin and E. Cand\`es.
Compressive Shift Retrieval
Henrik Ohlsson, Yonina C. Eldar, Allen Y. Yang, Shankar S. Sastry
(Submitted on 20 Mar 2013)
The classical shift retrieval problem considers two signals in vector form that are related by a cyclic shift. In this paper, we develop a compressive variant where the measurement of the signals is undersampled. While the standard procedure to shift retrieval is to maximize the real part of their dot product, we show that the shift can be exactly recovered from the corresponding compressed measurements if the sensing matrix satisfies certain conditions. A special case is the partial Fourier matrix. In this setting we show that the true shift can be found by as low as two measurements. We further show that the shift can often be recovered when the measurements are perturbed by noise.
Universal Numerical Encoder and Profiler Reduces Computing's Memory Wall with Software, FPGA, and SoC Implementations
Albert Wegener
(Submitted on 20 Mar 2013)
In the multicore era, the time to computational results is increasingly determined by how quickly operands are accessed by cores, rather than by the speed of computation per operand. From high-performance computing (HPC) to mobile application processors, low multicore utilization rates result from the slowness of accessing off-chip operands, i.e. the memory wall. The APplication AXcelerator (APAX) universal numerical encoder reduces computing's memory wall by compressing numerical operands (integers and floats), thereby decreasing CPU access time by 3:1 to 10:1 as operands stream between memory and cores. APAX encodes numbers using a low-complexity algorithm designed both for time series sensor data and for multi-dimensional data, including images. APAX encoding parameters are determined by a profiler that quantifies the uncertainty inherent in numerical datasets and recommends encoding parameters reflecting this uncertainty. Compatible software, FPGA, and systemon-chip (SoC) implementations efficiently support encoding rates between 150 MByte/sec and 1.5 GByte/sec at low power. On 25 integer and floating-point datasets, we achieved encoding rates between 3:1 and 10:1, with average correlation of 0.999959, while accelerating computational "time to results."
Greedy Feature Selection for Subspace Clustering
Eva L. Dyer, Aswin C. Sankaranarayanan, Richard G. Baraniuk
(Submitted on 19 Mar 2013)
Unions of subspaces are powerful nonlinear signal models for collections of high-dimensional data. However, existing methods that exploit this structure require that the subspaces the signals of interest occupy be known a priori or be learned from the data directly. In this work, we analyze the performance of greedy feature selection strategies for learning unions of subspaces from an ensemble of data. We develop sufficient conditions that are required for orthogonal matching pursuit (OMP) to recover subsets of points from the ensemble that live in the same subspace, a property we refer to as exact feature selection (EFS). Following this analysis, we provide an empirical study of greedy feature selection strategies for subspace clustering and characterize the gap between sparse recovery methods and nearest neighbor (NN)-based approaches. We demonstrate that the gap between sparse recovery and NN methods is particularly pronounced when the tiling of subspaces in the ensemble is sparse, suggesting that sparse recovery methods can be used in a number of regimes where nearest neighbor approaches fail to reveal the subspace membership of points in the ensemble.
Gradient methods for convex minimization: better rates under weaker conditions
Hui Zhang, Wotao Yin
(Submitted on 19 Mar 2013)
The convergence behavior of gradient methods for minimizing convex differentiable functions is one of the core questions in convex optimization. This paper shows that their well-known complexities can be achieved under conditions weaker than the commonly accepted ones. We relax the common gradient Lipschitz-continuity condition and strong convexity condition to ones that hold only over certain line segments. Specifically, we establish complexities $O(\frac{R}{\epsilon})$ and $O(\sqrt{\frac{R}{\epsilon}})$ for the ordinary and accelerate gradient methods, respectively, assuming that $\nabla f$ is Lipschitz continuous with constant $R$ over the line segment joining $x$ and $x-\frac{1}{R}\nabla f$ for each $x\in\dom f$. Then we improve them to $O(\frac{R}{\nu}\log(\frac{1}{\epsilon}))$ and $O(\sqrt{\frac{R}{\nu}}\log(\frac{1}{\epsilon}))$ for function $f$ that also satisfies the secant inequality $\ < \nabla f(x), x- x^*\ > \ge \nu\|x-x^*\|^2$ for each $x\in \dom f$ and its projection $x^*$ to the minimizer set of $f$. The secant condition is also shown to be necessary for the geometric decay of solution error. Not only are the relaxed conditions met by more functions, the restrictions give smaller $R$ and larger $\nu$ than they are without the restrictions and thus lead to better complexity bounds. We apply these results to sparse optimization and demonstrate a faster algorithm.
A General Iterative Shrinkage and Thresholding Algorithm for Non-convex Regularized Optimization Problems
Pinghua Gong, Changshui Zhang, Zhaosong Lu, Jianhua Huang, Jieping Ye
(Submitted on 18 Mar 2013)
Non-convex sparsity-inducing penalties have recently received considerable attentions in sparse learning. Recent theoretical investigations have demonstrated their superiority over the convex counterparts in several sparse learning settings. However, solving the non-convex optimization problems associated with non-convex penalties remains a big challenge. A commonly used approach is the Multi-Stage (MS) convex relaxation (or DC programming), which relaxes the original non-convex problem to a sequence of convex problems. This approach is usually not very practical for large-scale problems because its computational cost is a multiple of solving a single convex problem. In this paper, we propose a General Iterative Shrinkage and Thresholding (GIST) algorithm to solve the nonconvex optimization problem for a large class of non-convex penalties. The GIST algorithm iteratively solves a proximal operator problem, which in turn has a closed-form solution for many commonly used penalties. At each outer iteration of the algorithm, we use a line search initialized by the Barzilai-Borwein (BB) rule that allows finding an appropriate step size quickly. The paper also presents a detailed convergence analysis of the GIST algorithm. The efficiency of the proposed algorithm is demonstrated by extensive experiments on large-scale data sets.
Toward real-time quantum imaging with a single pixel camera
B.J. Lawrie, R.C. Pooser
(Submitted on 15 Mar 2013)
We present a workbench for the study of real-time quantum imaging by measuring the frame-by-frame quantum noise reduction of multi-spatial-mode twin beams generated by four wave mixing in Rb vapor. Exploiting the multiple spatial modes of this squeezed light source, we utilize spatial light modulators to selectively pass macropixels of quantum correlated modes from each of the twin beams to a high quantum efficiency balanced detector. In low-light-level imaging applications, the ability to measure the quantum correlations between individual spatial modes and macropixels of spatial modes with a single pixel camera will facilitate compressive quantum imaging with sensitivity below the photon shot noise limit.
Sparse approximation and recovery by greedy algorithms
Eugene Livshitz, Vladimir Temlyakov
(Submitted on 14 Mar 2013)
We study sparse approximation by greedy algorithms. Our contribution is two-fold. First, we prove exact recovery with high probability of random $K$-sparse signals within $\lceil K(1+\e)\rceil$ iterations of the Orthogonal Matching Pursuit (OMP). This result shows that in a probabilistic sense the OMP is almost optimal for exact recovery. Second, we prove the Lebesgue-type inequalities for the Weak Chebyshev Greedy Algorithm, a generalization of the Weak Orthogonal Matching Pursuit to the case of a Banach space. The main novelty of these results is a Banach space setting instead of a Hilbert space setting. However, even in the case of a Hilbert space our results add some new elements to known results on the Lebesque-type inequalities for the RIP dictionaries. Our technique is a development of the recent technique created by Zhang.
Tractability of Interpretability via Selection of Group-Sparse Models
Luca Baldassarre, Nirav Bhan, Volkan Cevher, Anastasios Kyrillidis
(Submitted on 13 Mar 2013)
Group-based sparsity models are proven instrumental in linear regression problems for recovering signals from much fewer measurements than standard compressive sensing. The main promise of these models is the recovery of "interpretable" signals along with the identification of their constituent groups. To this end, we establish a combinatorial framework for group-model selection problems and highlight the underlying tractability issues revolving around such notions of interpretability when the regression matrix is simply the identity operator. We show that, in general, claims of correctly identifying the groups with convex relaxations would lead to polynomial time solution algorithms for a well-known NP-hard problem, called the weighted maximum cover problem. Instead, leveraging a graph-based understanding of group models, we describe group structures which enable correct model identification in polynomial time via dynamic programming. We also show that group structures that lead to totally unimodular constraints have tractable discrete as well as convex relaxations. Finally, we study the Pareto frontier of budgeted group-sparse approximations for the tree-based sparsity model of \cite{baraniuk2010model} and illustrate identification and computation trade-offs between our framework and the existing convex relaxations.
Kernel Sparse Models for Automated Tumor Segmentation
Jayaraman J. Thiagarajan, Karthikeyan Natesan Ramamurthy, Deepta Rajan, Anup Puri, David Frakes, Andreas Spanias
(Submitted on 11 Mar 2013)
In this paper, we propose sparse coding-based approaches for segmentation of tumor regions from MR images. Sparse coding with data-adapted dictionaries has been successfully employed in several image recovery and vision problems. The proposed approaches obtain sparse codes for each pixel in brain magnetic resonance images considering their intensity values and location information. Since it is trivial to obtain pixel-wise sparse codes, and combining multiple features in the sparse coding setup is not straightforward, we propose to perform sparse coding in a high-dimensional feature space where non-linear similarities can be effectively modeled. We use the training data from expert-segmented images to obtain kernel dictionaries with the kernel K-lines clustering procedure. For a test image, sparse codes are computed with these kernel dictionaries, and they are used to identify the tumor regions. This approach is completely automated, and does not require user intervention to initialize the tumor regions in a test image. Furthermore, a low complexity segmentation approach based on kernel sparse codes, which allows the user to initialize the tumor region, is also presented. Results obtained with both the proposed approaches are validated against manual segmentation by an expert radiologist, and the proposed methods lead to accurate tumor identification.
Predictive Correlation Screening: Application to Two-stage Predictor Design in High Dimension
Hamed Firouzi, Bala Rajaratnam, Alfred Hero
(Submitted on 10 Mar 2013)
We introduce a new approach to variable selection, called Predictive Correlation Screening, for predictor design. Predictive Correlation Screening (PCS) implements false positive control on the selected variables, is well suited to small sample sizes, and is scalable to high dimensions. We establish asymptotic bounds for Familywise Error Rate (FWER), and resultant mean square error of a linear predictor on the selected variables. We apply Predictive Correlation Screening to the following two-stage predictor design problem. An experimenter wants to learn a multivariate predictor of gene expression based on successive biological samples assayed on mRNA arrays. She assays the whole genome on a few samples and from these assays she selects a small number of variables using Predictive Correlation Screening. To reduce assay cost, she subsequently assays only the selected variables on the remaining samples, to learn the predictor coefficients. We show superiority of Predictive Correlation Screening relative to LASSO and correlation learning in terms of performance and computational complexity.
l_0 Norm Constraint LMS Algorithm for Sparse System Identification
Yuantao Gu, Jian Jin, Shunliang Mei
(Submitted on 9 Mar 2013)
In order to improve the performance of Least Mean Square (LMS) based system identification of sparse systems, a new adaptive algorithm is proposed which utilizes the sparsity property of such systems. A general approximating approach on $l_0$ norm -- a typical metric of system sparsity, is proposed and integrated into the cost function of the LMS algorithm. This integration is equivalent to add a zero attractor in the iterations, by which the convergence rate of small coefficients, that dominate the sparse system, can be effectively improved. Moreover, using partial updating method, the computational complexity is reduced. The simulations demonstrate that the proposed algorithm can effectively improve the performance of LMS-based identification algorithms on sparse system.
New Understanding of the Bethe Approximation and the Replica Method
Ryuhei Mori
(Submitted on 9 Mar 2013)
In this thesis, new generalizations of the Bethe approximation and new understanding of the replica method are proposed. The Bethe approximation is an efficient approximation for graphical models, which gives an asymptotically accurate estimate of the partition function for many graphical models. The Bethe approximation explains the well-known message passing algorithm, belief propagation, which is exact for tree graphical models. It is also known that the cluster variational method gives the generalized Bethe approximation, called the Kikuchi approximation, yielding the generalized belief propagation. In the thesis, a new series of generalization of the Bethe approximation is proposed, which is named the asymptotic Bethe approximation. The asymptotic Bethe approximation is derived from the characterization of the Bethe free energy using graph covers, which was recently obtained by Vontobel. The asymptotic Bethe approximation can be expressed in terms of the edge zeta function by using Watanabe and Fukumizu's result about the Hessian of the Bethe entropy. The asymptotic Bethe approximation is confirmed to be better than the conventional Bethe approximation on some conditions. For this purpose, Chertkov and Chernyak's loop calculus formula is employed, which shows that the error of the Bethe approximation can be expressed as a sum of weights corresponding to generalized loops, and generalized for non-binary finite alphabets by using concepts of information geometry.
Bayesian Compressed Regression
Rajarshi Guhaniyogi, David B. Dunson
(Submitted on 4 Mar 2013 (v1), last revised 22 Mar 2013 (this version, v2))
As an alternative to variable selection or shrinkage in high dimensional regression, we propose to randomly compress the predictors prior to analysis. This dramatically reduces storage and computational bottlenecks, performing well when the predictors can be projected to a low dimensional linear subspace with minimal loss of information about the response. As opposed to existing Bayesian dimensionality reduction approaches, the exact posterior distribution conditional on the compressed data is available analytically, speeding up computation by many orders of magnitude while also bypassing robustness issues due to convergence and mixing problems with MCMC. Model averaging is used to reduce sensitivity to the random projection matrix, while accommodating uncertainty in the subspace dimension. Strong theoretical support is provided for the approach by showing near parametric convergence rates for the predictive density in the large p small n asymptotic paradigm. Practical performance relative to competitors is illustrated in simulations and real data applications.
Random Subdictionaries and Coherence Conditions for Sparse Signal Recovery
Alexander Barg, Arya Mazumdar, Rongrong Wang
(Submitted on 7 Mar 2013)
The most frequently used condition for sampling matrices employed in compressive sampling is the restricted isometry (RIP) property of the matrix when restricted to sparse signals. At the same time, imposing this condition makes it difficult to find explicit matrices that support recovery of signals from sketches of the optimal (smallest possible)dimension. A number of attempts have been made to relax or replace the RIP property in sparse recovery algorithms. We focus on the relaxation under which the near-isometry property holds for most rather than for all submatrices of the sampling matrix, known as statistical RIP or StRIP condition. We show that sampling matrices of dimensions $m\times N$ with maximum coherence $\mu=O((k\log^3 N)^{-1/4})$ and mean square coherence $\bar \mu^2=O(1/(k\log N))$ support stable recovery of $k$-sparse signals using Basis Pursuit. These assumptions are satisfied in many examples. As a result, we are able to construct sampling matrices that support recovery with low error for sparsity $k$ higher than $\sqrt m,$ which exceeds the range of parameters of the known classes of RIP matrices.
On Robust Face Recognition via Sparse Encoding: the Good, the Bad, and the Ugly
Yongkang Wong, Mehrtash T. Harandi, Conrad Sanderson
(Submitted on 7 Mar 2013)
In the field of face recognition, Sparse Representation (SR) has received considerable attention during the past few years. Most of the relevant literature focuses on holistic descriptors in closed-set identification applications. The underlying assumption in SR-based methods is that each class in the gallery has sufficient samples and the query lies on the subspace spanned by the gallery of the same class. Unfortunately, such assumption is easily violated in the more challenging face verification scenario, where an algorithm is required to determine if two faces (where one or both have not been seen before) belong to the same person. In this paper, we first discuss why previous attempts with SR might not be applicable to verification problems. We then propose an alternative approach to face verification via SR. Specifically, we propose to use explicit SR encoding on local image patches rather than the entire face. The obtained sparse signals are pooled via averaging to form multiple region descriptors, which are then concatenated to form an overall face descriptor. Due to the deliberate loss spatial relations within each region (caused by averaging), the resulting descriptor is robust to misalignment & various image deformations. Within the proposed framework, we evaluate several SR encoding techniques: l1-minimisation, Sparse Autoencoder Neural Network (SANN), and an implicit probabilistic technique based on Gaussian Mixture Models. Thorough experiments on AR, FERET, exYaleB, BANCA and ChokePoint datasets show that the proposed local SR approach obtains considerably better and more robust performance than several previous state-of-the-art holistic SR methods, in both verification and closed-set identification problems. The experiments also show that l1-minimisation based encoding has a considerably higher computational than the other techniques, but leads to higher recognition rates.
A Fast Iterative Bayesian Inference Algorithm for Sparse Channel Estimation
Niels Lovmand Pedersen, Carles Navarro Manchón Bernard Henri Fleury
(Submitted on 6 Mar 2013)
In this paper, we present a Bayesian channel estimation algorithm for multicarrier receivers based on pilot symbol observations. The inherent sparse nature of wireless multipath channels is exploited by modeling the prior distribution of multipath components' gains with a hierarchical representation of the Bessel K probability density function; a highly efficient, fast iterative Bayesian inference method is then applied to the proposed model. The resulting estimator outperforms other state-of-the-art Bayesian and non-Bayesian estimators, either by yielding lower mean squared estimation error or by attaining the same accuracy with improved convergence rate, as shown in our numerical evaluation.
Impulsive Noise Mitigation in Powerline Communications Using Sparse Bayesian Learning
Jing Lin, Marcel Nassar, Brian L. Evans
(Submitted on 5 Mar 2013)
Additive asynchronous and cyclostationary impulsive noise limits communication performance in OFDM powerline communication (PLC) systems. Conventional OFDM receivers assume additive white Gaussian noise and hence experience degradation in communication performance in impulsive noise. Alternate designs assume a parametric statistical model of impulsive noise and use the model parameters in mitigating impulsive noise. These receivers require overhead in training and parameter estimation, and degrade due to model and parameter mismatch, especially in highly dynamic environments. In this paper, we model impulsive noise as a sparse vector in the time domain without any other assumptions, and apply sparse Bayesian learning methods for estimation and mitigation without training. We propose three iterative algorithms with different complexity vs. performance trade-offs: (1) we utilize the noise projection onto null and pilot tones to estimate and subtract the noise impulses; (2) we add the information in the data tones to perform joint noise estimation and OFDM detection; (3) we embed our algorithm into a decision feedback structure to further enhance the performance of coded systems. When compared to conventional OFDM PLC receivers, the proposed receivers achieve SNR gains of up to 9 dB in coded and 10 dB in uncoded systems in the presence of impulsive noise.
Recursive Sparse Recovery in Large but Structured Noise - Part 2
Chenlu Qiu, Namrata Vaswani
(Submitted on 5 Mar 2013)
We study the problem of recursively recovering a time sequence of sparse vectors, St, from measurements Mt := St + Lt that are corrupted by structured noise Lt which is dense and can have large magnitude. The structure that we require is that Lt should lie in a low dimensional subspace that is either fixed or changes "slowly enough"; and the eigenvalues of its covariance matrix are "clustered". We do not assume any model on the sequence of sparse vectors. Their support sets and their nonzero element values may be either independent or correlated over time (usually in many applications they are correlated). The only thing required is that there be some support change every so often. We introduce a novel solution approach called Recursive Projected Compressive Sensing with cluster-PCA (ReProCS-cPCA) that addresses some of the limitations of earlier work. Under mild assumptions, we show that, with high probability, ReProCS-cPCA can exactly recover the support set of St at all times; and the reconstruction errors of both St and Lt are upper bounded by a time-invariant and small value.
On sparse sensing and sparse sampling of coded signals at sub-Landau rates
Michael Peleg, Shlomo Shamai
(Submitted on 1 Mar 2013)
Advances of information-theoretic understanding of sparse sampling of continuous uncoded signals at sampling rates exceeding the Landau rate were reported in recent works. This work examines sparse sampling of coded signals at sub-Landau sampling rates. It is shown that with coded signals the Landau condition may be relaxed and the sampling rate required for signal reconstruction and for support detection can be lower than the effective bandwidth. Equivalently, the number of measurements in the corresponding sparse sensing problem can be smaller than the support size. Tight bounds on information rates and on signal and support detection performance are derived for the Gaussian sparsely sampled channel and for the frequency-sparse channel using the context of state dependent channels. Support detection results are verified by a simulation. When the system is high-dimensional the required SNR is shown to be finite but high and rising with decreasing sampling rate, in some practical applications it can be lowered by reducing the a-priory uncertainty about the support e.g. by concentrating the frequency support into a finite number of subbands.
Randomized Low-Memory Singular Value Projection
Stephen Becker, Volkan Cevher, Anastasios Kyrillidis
(Submitted on 1 Mar 2013 (v1), last revised 19 Mar 2013 (this version, v2))
Affine rank minimization algorithms typically rely on calculating the gradient of a data error followed by singular value decompositions at every iteration. Because these two steps are expensive, heuristics are often used. In this paper, we propose one recovery scheme that merges the two steps and show that it actually admits provable recovery guarantees while operating on space proportional to the degrees of freedom in the problem.
An Augmented Lagrangian Method for Conic Convex Programming
Necdet Serhat Aybat, Garud Iyengar
(Submitted on 26 Feb 2013)
We propose a new first-order augmented Lagrangian algorithm ALCC for solving convex conic programs of the form min{rho(x)+gamma(x): Ax-b in K, x in chi}, where rho and gamma are closed convex functions, and gamma has a Lipschitz continuous gradient, A is mxn real matrix, K is a closed convex cone, and chi is a "simple" convex compact set such that optimization problems of the form min{rho(x)+|x-x0|_2^2: x in chi} can be efficiently solved for any given x0. We show that any limit point of the primal ALCC iterates is an optimal solution of the conic convex problem, and the dual ALCC iterates have a unique limit point that is a Karush-Kuhn-Tucker (KKT) point of the conic program. We also show that for any epsilon>0, the primal ALCC iterates are epsilon-feasible and epsilon optimal after O(log(1/epsilon)) iterations which require solving O(1/epsilon log(1/epsilon)) problems of the form min{rho(x)+|x-x0|_2^2: x in chi}.
Super-resolution via superset selection and pruning
Laurent Demanet, Deanna Needell, Nam Nguyen
(Submitted on 26 Feb 2013)
We present a pursuit-like algorithm that we call the "superset method" for recovery of sparse vectors from consecutive Fourier measurements in the super-resolution regime. The algorithm has a subspace identification step that hinges on the translation invariance of the Fourier transform, followed by a removal step to estimate the solution's support. The superset method is always successful in the noiseless regime (unlike L1-minimization) and generalizes to higher dimensions (unlike the matrix pencil method). Relative robustness to noise is demonstrated numerically.
Sound localization using compressive sensing
Hong Jiang, Boyd Mathews, Paul Wilford
(Submitted on 28 Feb 2013)
In a sensor network with remote sensor devices, it is important to have a method that can accurately localize a sound event with a small amount of data transmitted from the sensors. In this paper, we propose a novel method for localization of a sound source using compressive sensing. Instead of sampling a large amount of data at the Nyquist sampling rate in time domain, the acoustic sensors take compressive measurements integrated in time. The compressive measurements can be used to accurately compute the location of a sound source.
Ensemble Sparse Models for Image Analysis
Karthikeyan Natesan Ramamurthy, Jayaraman J. Thiagarajan, Prasanna Sattigeri, Andreas Spanias
(Submitted on 27 Feb 2013)
Sparse representations with learned dictionaries have been successful in several image analysis applications. In this paper, we propose and analyze the framework of ensemble sparse models, and demonstrate their utility in image restoration and unsupervised clustering. The proposed ensemble model approximates the data as a linear combination of approximations from multiple \textit{weak} sparse models. Theoretical analysis of the ensemble model reveals that even in the worst-case, the ensemble can perform better than any of its constituent individual models. The dictionaries corresponding to the individual sparse models are obtained using either random example selection or boosted approaches. Boosted approaches learn one dictionary per round such that the dictionary learned in a particular round is optimized for the training examples having high reconstruction error in the previous round. Results with compressed recovery show that the ensemble representations lead to a better performance compared to using a single dictionary obtained with the conventional alternating minimization approach. The proposed ensemble models are also used for single image superresolution, and we show that they perform comparably to the recent approaches. In unsupervised clustering, experiments show that the proposed model performs better than baseline approaches in several standard datasets.
Compressed Sensing with Sparse Binary Matrices: Instance Optimal Error Guarantees in Near-Optimal Time
M. A. Iwen
(Submitted on 24 Feb 2013)
A compressed sensing method consists of a rectangular measurement matrix, $M \in \mathbbm{R}^{m \times N}$ with $m \ll N$, together with an associated recovery algorithm, $\mathcal{A}: \mathbbm{R}^m \rightarrow \mathbbm{R}^N$. Compressed sensing methods aim to construct a high quality approximation to any given input vector ${\bf x} \in \mathbbm{R}^N$ using only $M {\bf x} \in \mathbbm{R}^m$ as input. In particular, we focus herein on instance optimal nonlinear approximation error bounds for $M$ and $\mathcal{A}$ of the form $ \| {\bf x} - \mathcal{A} (M {\bf x}) \|_p \leq \| {\bf x} - {\bf x}^{\rm opt}_k \|_p + C k^{1/p - 1/q} \| {\bf x} - {\bf x}^{\rm opt}_k \|_q$ for ${\bf x} \in \mathbbm{R}^N$, where ${\bf x}^{\rm opt}_k$ is the best possible $k$-term approximation to ${\bf x}$.
In this paper we develop a compressed sensing method whose associated recovery algorithm, $\mathcal{A}$, runs in $O((k \log k) \log N)$-time, matching a lower bound up to a $O(\log k)$ factor. This runtime is obtained by using a new class of sparse binary compressed sensing matrices of near optimal size in combination with sublinear-time recovery techniques motivated by sketching algorithms for high-volume data streams. The new class of matrices is constructed by randomly subsampling rows from well-chosen incoherent matrix constructions which already have a sub-linear number of rows. As a consequence, fewer random bits than previously required are needed in order to select the rows utilized by the fast reconstruction algorithms considered herein.
A Multi-Scale Spatial Model for RSS-based Device-Free Localization
Ossi Kaltiokallio, Maurizio Bocca, Neal Patwari
(Submitted on 24 Feb 2013)
RSS-based device-free localization (DFL) monitors changes in the received signal strength (RSS) measured by a network of static wireless nodes to locate people without requiring them to carry or wear any electronic device. Current models assume that the spatial impact area, i.e., the area in which a person affects a link's RSS, has constant size. This paper shows that the spatial impact area varies considerably for each link. Data from extensive experiments are used to derive a multi-scale spatial weight model that is a function of the fade level, i.e., the difference between the predicted and measured RSS, and of the direction of RSS change. In addition, a measurement model is proposed which gives a probability of a person locating inside the derived spatial model for each given RSS measurement. A real-time radio tomographic imaging system is described which uses channel diversity and the presented models. Experiments in an open indoor environment, in a typical one-bedroom apartment and in a through-wall scenario are conducted to determine the accuracy of the system. We demonstrate that the new system is capable of localizing and tracking a person with high accuracy (<0 .30="" all="" blockquote="" change="" environments="" in="" m="" model="" need="" parameters.="" the="" to="" without="">
Sparse Signal Estimation by Maximally Sparse Convex Optimization
Ivan W. Selesnick, Ilker Bayram
(Submitted on 22 Feb 2013)
This paper addresses the problem of sparsity penalized least squares for applications in sparse signal processing, e.g. sparse deconvolution. This paper aims to induce sparsity more strongly than L1 norm regularization, while avoiding non-convex optimization. For this purpose, this paper describes the design and use of non-convex penalty functions (regularizers) constrained so as to ensure the convexity of the total cost function, F, to be minimized. The method is based on parametric penalty functions, the parameters of which are constrained to ensure convexity of F. It is shown that optimal parameters can be obtained by semidefinite programming (SDP). This maximally sparse convex (MSC) approach yields maximally non-convex sparsity-inducing penalty functions constrained such that the total cost function, F, is convex. It is demonstrated that iterative MSC (IMSC) can yield solutions substantially more sparse than the standard convex sparsity-inducing approach, i.e., L1 norm minimization.
Stable phase retrieval with low-redundancy frames
Bernhard G. Bodmann, Nathaniel Hammen
(Submitted on 22 Feb 2013)
We investigate the recovery of vectors from magnitudes of frame coefficients when the frames have a low redundancy, meaning a small number of frame vectors compared to the dimension of the Hilbert space. We first show that for vectors in d dimensions, 4d-4 suitably chosen frame vectors are sufficient to uniquely determine each signal, up to an overall unimodular constant, from the magnitudes of its frame coefficients. Then we discuss the effect of noise and show that 8d-4 frame vectors provide a stable recovery if part of the frame coefficients is bounded away from zero. In this regime, perturbing the magnitudes of the frame coefficients by noise that is sufficiently small results in a recovery error that is at most proportional to the noise level.
q-ary Compressive Sensing
Youssef Mroueh, Lorenzo Rosasco
(Submitted on 21 Feb 2013)
We introduce q-ary compressive sensing, an extension of 1-bit compressive sensing. We propose a novel sensing mechanism and a corresponding recovery procedure. The recovery properties of the proposed approach are analyzed both theoretically and empirically. Results in 1-bit compressive sensing are recovered as a special case. Our theoretical results suggest a tradeoff between the quantization parameter q, and the number of measurements m in the control of the error of the resulting recovery algorithm, as well its robustness to noise.
Is Matching Pursuit Solving Convex Problems?
Mingkui Tan, Ivor W. Tsang, Li Wang
(Submitted on 20 Feb 2013)
Sparse recovery ({\tt SR}) has emerged as a very powerful tool for signal processing, data mining and pattern recognition. To solve {\tt SR}, many efficient matching pursuit (\texttt{MP}) algorithms have been proposed. However, it is still not clear whether {\tt SR} can be formulated as a convex problem that is solvable using \texttt{MP} algorithms. To answer this, in this paper, a novel convex relaxation model is presented, which is solved by a general matching pursuit (\texttt{GMP}) algorithm under the convex programming framework. {\tt GMP} has several advantages over existing methods. At first, it solves a convex problem and guarantees to converge to a optimum. In addition, with $\ell_1$-regularization, it can recover any $k$-sparse signals if the restricted isometry constant $\sigma_k\leq 0.307-\nu$, where $\nu$ can be arbitrarily close to 0. Finally, when dealing with a batch of signals, the computation burden can be much reduced using a batch-mode \texttt{GMP}. Comprehensive numerical experiments show that \texttt{GMP} achieves better performance than other methods in terms of sparse recovery ability and efficiency. We also apply \texttt{GMP} to face recognition tasks on two well-known face databases, namely, \emph{{Extended using}} and \emph{AR}. Experimental results demonstrate that {\tt GMP} can achieve better recognition performance than the considered state-of-the-art methods within acceptable time. {Particularly, the batch-mode {\tt GMP} can be up to 500 times faster than the considered $\ell_1$ methods.}
An SVD-free Pareto curve approach to rank minimization
Aleksandr Y. Aravkin, Rajiv Mittal, Hassan Mansour, Ben Recht, Felix J. Herrmann
(Submitted on 20 Feb 2013)
Recent SVD-free matrix factorization formulations have enabled rank optimization for extremely large-scale systems (millions of rows and columns). In this paper, we consider rank-regularized formulations that only require a target data-fitting error level, and propose an algorithm for the corresponding problem. We illustrate the advantages of the new approach using the Netflix prob- lem, and use it to obtain high quality results for seismic trace interpolation, a key application in exploration geophysics. We show that factor rank can be easily adjusted as the inversion proceeds, and propose a weighted extension that allows known subspace information to improve the results of matrix completion formulations. Using these methods, we obtain high-quality reconstructions for large scale seismic interpolation problems with real data.
Moving target inference with hierarchical Bayesian models in synthetic aperture radar imagery
Gregory E. Newstadt, Edmund G. Zelnio, Alfred O. Hero III
(Submitted on 19 Feb 2013)
In synthetic aperture radar (SAR), images are formed by focusing the response of stationary objects to a single spatial location. On the other hand, moving targets cause phase errors in the standard formation of SAR images that cause displacement and defocusing effects. SAR imagery also contains significant sources of non-stationary spatially-varying noises, including antenna gain discrepancies, angular scintillation (glints) and complex speckle. In order to account for this intricate phenomenology, this work combines the knowledge of the physical, kinematic, and statistical properties of SAR imaging into a single unified Bayesian structure that simultaneously (a) estimates the nuisance parameters such as clutter distributions and antenna miscalibrations and (b) estimates the target signature required for detection/inference of the target state. Moreover, we provide a Monte Carlo estimate of the posterior distribution for the target state and nuisance parameters that infers the parameters of the model directly from the data, largely eliminating tuning of algorithm parameters. We demonstrate that our algorithm competes at least as well on a synthetic dataset as state-of-the-art algorithms for estimating sparse signals. Finally, performance analysis on a measured dataset demonstrates that the proposed algorithm is robust at detecting/estimating targets over a wide area and performs at least as well as popular algorithms for SAR moving target detection.
Compressive Classification
Hugo Reboredo (1), Francesco Renna (1), Robert Calderbank (2), Miguel R. D. Rodrigues (3) ((1) Instituto de Telecomunicações, Universidade do Porto, Portugal, (2) Department of ECE, Duke University, NC, USA, (3) Department of E&EE, University College London, UK,)
(Submitted on 19 Feb 2013)
This paper derives fundamental limits associated with compressive classification of Gaussian mixture source models. In particular, we offer an asymptotic characterization of the behavior of the (upper bound to the) misclassification probability associated with the optimal Maximum-A-Posteriori (MAP) classifier that depends on quantities that are dual to the concepts of diversity gain and coding gain in multi-antenna communications. The diversity, which is shown to determine the rate at which the probability of misclassification decays in the low noise regime, is shown to depend on the geometry of the source, the geometry of the measurement system and their interplay. The measurement gain, which represents the counterpart of the coding gain, is also shown to depend on geometrical quantities. It is argued that the diversity order and the measurement gain also offer an optimization criterion to perform dictionary learning for compressive classification applications.
Saving phase: Injectivity and stability for phase retrieval
Afonso S. Bandeira, Jameson Cahill, Dustin G. Mixon, Aaron A. Nelson
(Submitted on 19 Feb 2013 (v1), last revised 14 Mar 2013 (this version, v2))
Recent advances in convex optimization have led to new strides in the phase retrieval problem over finite-dimensional vector spaces. However, certain fundamental questions remain: What sorts of measurement vectors uniquely determine every signal up to a global phase factor, and how many are needed to do so? Furthermore, which measurement ensembles lend stability? This paper presents several results that address each of these questions. We begin by characterizing injectivity, and we identify that the complement property is indeed a necessary condition in the complex case. We then pose a conjecture that 4M-4 generic measurement vectors are both necessary and sufficient for injectivity in M dimensions, and we prove this conjecture in the special cases where M=2,3. Next, we shift our attention to stability, both in the worst and average cases. Here, we characterize worst-case stability in the real case by introducing a numerical version of the complement property. This new property bears some resemblance to the restricted isometry property of compressed sensing and can be used to derive a sharp lower Lipschitz bound on the intensity measurement mapping. Localized frames are shown to lack this property (suggesting instability), whereas Gaussian random measurements are shown to satisfy this property with high probability. We conclude by presenting results that use a stochastic noise model in both the real and complex cases, and we leverage Cramer-Rao lower bounds to identify stability with stronger versions of the injectivity characterizations.
Adaptive low rank and sparse decomposition of video using compressive sensing
Fei Yang, Hong Jiang, Zuowei Shen, Wei Deng, Dimitris Metaxas
(Submitted on 6 Feb 2013)
We address the problem of reconstructing and analyzing surveillance videos using compressive sensing. We develop a new method that performs video reconstruction by low rank and sparse decomposition adaptively. Background subtraction becomes part of the reconstruction. In our method, a background model is used in which the background is learned adaptively as the compressive measurements are processed. The adaptive method has low latency, and is more robust than previous methods. We will present experimental results to demonstrate the advantages of the proposed method.
Wideband Spectrum Sensing for Cognitive Radio Networks: A Survey
Hongjian Sun, Arumugam Nallanathan, Cheng-Xiang Wang, Yunfei Chen
(Submitted on 7 Feb 2013 (v1), last revised 4 Mar 2013 (this version, v2))
Cognitive radio has emerged as one of the most promising candidate solutions to improve spectrum utilization in next generation cellular networks. A crucial requirement for future cognitive radio networks is wideband spectrum sensing: secondary users reliably detect spectral opportunities across a wide frequency range. In this article, various wideband spectrum sensing algorithms are presented, together with a discussion of the pros and cons of each algorithm and the challenging issues. Special attention is paid to the use of sub-Nyquist techniques, including compressive sensing and multi-channel sub-Nyquist sampling techniques.
Lensless Compressive Sensing Imaging
Gang Huang, Hong Jiang, Kim Matthews, Paul Wilford
(Submitted on 7 Feb 2013)
In this paper, we propose a lensless compressive sensing imaging architecture. The architecture consists of two components, an aperture assembly and a sensor. No lens is used. The aperture assembly consists of a two dimensional array of aperture elements. The transmittance of each aperture element is independently controllable. The sensor is a single detection element, such as a single photo-conductive cell. Each aperture element together with the sensor defines a cone of a bundle of rays, and the cones of the aperture assembly define the pixels of an image. Each pixel value of an image is the integration of the bundle of rays in a cone. The sensor is used for taking compressive measurements. Each measurement is the integration of rays in the cones modulated by the transmittance of the aperture elements. A compressive sensing matrix is implemented by adjusting the transmittance of the individual aperture elements according to the values of the sensing matrix. The proposed architecture is simple and reliable because no lens is used. Furthermore, the sharpness of an image from our device is only limited by the resolution of the aperture assembly, but not affected by blurring due to defocus. The architecture can be used for capturing images of visible lights, and other spectra such as infrared, or millimeter waves. Such devices may be used in surveillance applications for detecting anomalies or extracting features such as speed of moving objects. Multiple sensors may be used with a single aperture assembly to capture multi-view images simultaneously. A prototype was built by using a LCD panel and a photoelectric sensor for capturing images of visible spectrum.
Adaptive Compressive Spectrum Sensing for Wideband Cognitive Radios
Hongjian Sun, Wei-Yu Chiu, A. Nallanathan
(Submitted on 7 Feb 2013)
This letter presents an adaptive spectrum sensing algorithm that detects wideband spectrum using sub-Nyquist sampling rates. By taking advantage of compressed sensing (CS), the proposed algorithm reconstructs the wideband spectrum from compressed samples. Furthermore, an l2 norm validation approach is proposed that enables cognitive radios (CRs) to automatically terminate the signal acquisition once the current spectral recovery is satisfactory, leading to enhanced CR throughput. Numerical results show that the proposed algorithm can not only shorten the spectrum sensing interval, but also improve the throughput of wideband CRs.
Wideband Spectrum Sensing with Sub-Nyquist Sampling in Cognitive Radios
Hongjian Sun, Wei-Yu Chiu, Jing Jiang, Arumugam Nallanathan, H. Vincent Poor
(Submitted on 7 Feb 2013)
Multi-rate asynchronous sub-Nyquist sampling (MASS) is proposed for wideband spectrum sensing. Corresponding spectral recovery conditions are derived and the probability of successful recovery is given. Compared to previous approaches, MASS offers lower sampling rate, and is an attractive approach for cognitive radio networks.
Surveillance Video Processing Using Compressive Sensing
Hong Jiang, Wei Deng, Zuowei Shen
(Submitted on 8 Feb 2013)
A compressive sensing method combined with decomposition of a matrix formed with image frames of a surveillance video into low rank and sparse matrices is proposed to segment the background and extract moving objects in a surveillance video. The video is acquired by compressive measurements, and the measurements are used to reconstruct the video by a low rank and sparse decomposition of matrix. The low rank component represents the background, and the sparse component is used to identify moving objects in the surveillance video. The decomposition is performed by an augmented Lagrangian alternating direction method. Experiments are carried out to demonstrate that moving objects can be reliably extracted with a small amount of measurements.
A new compressive video sensing framework for mobile broadcast
Chengbo Li, Hong Jiang, Paul Wilford, Yin Zhang, Mike Scheutzow
(Submitted on 8 Feb 2013)
A new video coding method based on compressive sampling is proposed. In this method, a video is coded using compressive measurements on video cubes. Video reconstruction is performed by minimization of total variation (TV) of the pixelwise DCT coefficients along the temporal direction. A new reconstruction algorithm is developed from TVAL3, an efficient TV minimization algorithm based on the alternating minimization and augmented Lagrangian methods. Video coding with this method is inherently scalable, and has applications in mobile broadcast.
Efficient Data Gathering in Wireless Sensor Networks Based on Matrix Completion and Compressive Sensing
Jiping Xiong, Jian Zhao, Lei Chen
(Submitted on 9 Feb 2013)
Gathering data in an energy efficient manner in wireless sensor networks is an important design challenge. In wireless sensor networks, the readings of sensors always exhibit intra-temporal and inter-spatial correlations. Therefore, in this letter, we use low rank matrix completion theory to explore the inter-spatial correlation and use compressive sensing theory to take advantage of intra-temporal correlation. Our method, dubbed MCCS, can significantly reduce the amount of data that each sensor must send through network and to the sink, thus prolong the lifetime of the whole networks. Experiments using real datasets demonstrate the feasibility and efficacy of our MCCS method.
On the list decodability of random linear codes with large error rate
Mary Wootters
(Submitted on 9 Feb 2013)
It is well-known that a random q-ary code of rate \Omega(\epsilon^2) is list decodable up to radius (1 - 1/q - \epsilon) with list sizes on the order of 1/\epsilon^2, with probability 1 - o(1). However, until recently, a similar statement about random linear codes has until remained elusive. In a recent paper, Cheraghchi, Guruswami, and Velingker show a connection between list decodability of random linear codes and the Restricted Isometry Property from compressed sensing, and use this connection to prove that a random linear code of rate \Omega(\epsilon^2 / log^3(1/\epsilon)) achieves the list decoding properties above, with constant probability. We improve on their result to show that in fact we may take the rate to be \Omega(\epsilon^2), which is optimal, and further that the success probability is 1 - o(1), rather than constant. As an added benefit, our proof is relatively simple. Finally, we extend our methods to more general ensembles of linear codes. As an example, we show that randomly punctured Reed-Muller codes have the same list decoding properties as the original codes, even when the rate is improved to a constant.
Conditional Gradient Algorithms for Norm-Regularized Smooth Convex Optimization
Zaid Harchaoui, Anatoli Juditsky, Arkadi Nemirovski
(Submitted on 10 Feb 2013 (v1), last revised 7 Mar 2013 (this version, v3))
Motivated by some applications in signal processing and machine learning, we consider two convex optimization problems where, given a cone $K$, a norm $\|\cdot\|$ and a smooth convex function $f$, we want either 1) to minimize the norm over the intersection of the cone and a level set of $f$, or 2) to minimize over the cone the sum of $f$ and a multiple of the norm. We focus on the case where (a) the dimension of the problem is too large to allow for interior point algorithms, (b) $\|\cdot\|$ is "too complicated" to allow for computationally cheap Bregman projections required in the first order proximal algorithms. On the other hand, we assume that the intersection of the unit ball of $\|\cdot\|$ with $K$ allows for cheap Minimization Oracle capable to minimize linear forms over the intersection. Motivating examples are given by the nuclear norm and $K$ being the entire space of matrices, or the positive semidefinite cone in the space of symmetric matrices, and the Total Variation norm on the space of 2D images. We discuss versions of the Conditional Gradient algorithm (in its original form aimed at minimizing smooth convex functions over bounded domains given by minimization oracles) capable to handle our problems of interest, provide the related theoretical efficiency estimates and outline some applications.
Adaptive Space-Time Beamforming in Radar Systems
Rodrigo C. de Lamare
(Submitted on 10 Feb 2013)
The goal of this chapter is to review the recent work and advances in the area of space-time beamforming algorithms and their application to radar systems. These systems include phased-array \cite{melvin} and multi-input multi-output (MIMO) radar systems \cite{haimo_08}, mono-static and bi-static radar systems and other configurations \cite{melvin}. Furthermore, this chapter also describes in detail some of the most successful space-time beamforming algorithms that exploit low-rank and sparsity properties as well as the use of prior-knowledge to improve the performance of STAP algorithms in radar systems.
Compressed Sensing with Incremental Sparse Measurements
Xiaofu Wu, Zhen Yang, Lu Gan
(Submitted on 11 Feb 2013)
This paper proposes a verification-based decoding approach for reconstruction of a sparse signal with incremental sparse measurements. In its first step, the verification-based decoding algorithm is employed to reconstruct the signal with a fixed number of sparse measurements. Often, it may fail as the number of sparse measurements may be not enough, possibly due to an underestimate of the signal sparsity. However, we observe that even if this first recovery fails, many component samples of the sparse signal have been identified. Hence, it is natural to further employ incremental measurements tuned to the unidentified samples with known locations. This approach has been proven very efficiently by extensive simulations.
MR Image Reconstruction from Undersampled k-Space with Bayesian Dictionary Learning
Yue Huang, John Paisley, Xianbo Chen, Xinghao Ding, Feng Huang, Xiao-ping Zhang
(Submitted on 12 Feb 2013)
We develop an algorithm for reconstructing magnetic resonance images (MRI) from highly undersampled k-space data. While existing methods focus on either image-level or patch-level sparse regularization strategies, we present a regularization framework that uses both image and patch-level sparsity constraints. The proposed regularization enforces image-level sparsity in terms of spatial finite differences (total variation) and patch-wise sparsity through in situ dictionary learning. We use the beta-Bernoulli process as a Bayesian prior for dictionary learning, which adaptively infers the dictionary size, the sparsity of each patch and the noise parameters. In addition, we employ an efficient numerical algorithm based on the alternating direction method of multipliers (ADMM). We present empirical results on several MR images, which show that the proposed regularization framework can improve reconstruction accuracy over other methods.
Coherence and sufficient sampling densities for reconstruction in compressed sensing
Franz J. Király, Louis Theran
(Submitted on 12 Feb 2013)
We introduce a concept called coherence for signals and constraints in compressed sensing. In our setting, we assume that the signal can be observed in finitely many features, and the set of possibly observable feature combinations forms an analytic variety which models the compression constraints. We study the question how many random measurements of the feature components suffice to identify all features. We show that the asymptotics of the sufficient number of measurements is determined by the coherence of the signal; furthermore, if the constraints are algebraic, we show that in general the asymptotics depend only on the coherence of the constraints, and not on the true signal, and derive results which explain the form of known bounds in compressed sensing. We exemplify our approach by deriving sufficient sampling densities for low-rank matrix completion and distance matrix completion which are independent of the true matrix.
A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints
Ion Necoara, Andrei Patrascu
(Submitted on 13 Feb 2013)
In this paper we propose a variant of the random coordinate descent method for solving linearly constrained convex optimization problems with composite objective functions. If the smooth part of the objective function has Lipschitz continuous gradient, then we prove that our method obtains an $\epsilon$-optimal solution in ${\cal O}(N^2/\epsilon)$ iterations, where $N$ is the number of blocks. For the class of problems with cheap coordinate derivatives we show that the new method is faster than methods based on full-gradient information. Analysis for the rate of convergence in probability is also provided. For strongly convex functions our method converges linearly. Extensive numerical tests confirm that on very large problems, our method is much more numerically efficient than methods based on full gradient information.
Adaptive Temporal Compressive Sensing for Video
Xin Yuan, Jianbo Yang, Patrick Llull, Xuejun Liao, Guillermo Sapiro, David J. Brady, Lawrence Carin
(Submitted on 14 Feb 2013 (v1), last revised 15 Feb 2013 (this version, v2))
This paper introduces the concept of adaptive temporal compressive sensing (CS) for video. We propose a CS algorithm to adapt the compression ratio based on the scene's temporal complexity, computed from the compressed data, without compromising the quality of the reconstructed video. The temporal adaptivity is manifested by manipulating the integration time of the camera, opening the possibility to real-time implementation. The proposed algorithm is a generalized temporal CS approach that can be incorporated with a diverse set of existing hardware systems.
Analysis Based Blind Compressive Sensing
Julian Wörmann, Simon Hawe, Martin Kleinsteuber
(Submitted on 5 Feb 2013)
In this work we address the problem of blindly reconstructing compressively sensed signals by exploiting the co-sparse analysis model. In the analysis model it is assumed that a signal multiplied by an analysis operator results in a sparse vector. We propose an algorithm that learns the operator adaptively during the reconstruction process. The arising optimization problem is tackled via a geometric conjugate gradient approach. Different types of sampling noise are handled by simply exchanging the data fidelity term. Numerical experiments are performed for measurements corrupted with Gaussian as well as impulsive noise to show the effectiveness of our method.
Sharp RIP Bound for Sparse Signal and Low-Rank Matrix Recovery
T. Tony Cai, Anru Zhang
(Submitted on 6 Feb 2013)
This paper establishes a sharp condition on the restricted isometry property (RIP) for both the sparse signal recovery and low-rank matrix recovery. It is shown that if the measurement matrix $A$ satisfies the RIP condition $\delta_k^A<1 addition="" all="" and="" are="" at="" b="{\cal" based="" be="" beta="" blockquote="" both="" cal="" can="" cases="" condition.="" condition="" considered="" constrained="" delta_r="" do="" does="" ell_1="" exactly="" furthermore="" general="" given="" hold.="" if="" in="" inequalities="" is="" it="" k="" linear="" m="" map="" matrices="" minimization="" most="" noisy="" norm="" not="" nuclear="" of="" on="" oracle="" possible="" r="" rank="" recovered="" rip="" satisfies="" sharp="" signals="" similarly="" so="" sparse="" the="" then="" to="" under="" via="" when="" y="A\beta$.">
Adaptive Sparse Channel Estimation for Time-Variant MISO Communication Systems
Guan Gui, Wei Peng, Abolfazl Mehbodniya, Fumiyuki Adachi
(Submitted on 6 Feb 2013)
Channel estimation problem is one of the key technical issues in time-variant multiple-input single-output (MSIO) communication systems. To estimate the MISO channel, least mean square (LMS) algorithm is applied to adaptive channel estimation (ACE). Since the MISO channel is often described by sparse channel model, such sparsity can be exploited and then estimation performance can be improved by adaptive sparse channel estimation (ASCE) methods using sparse LMS algorithms. However, conventional ASCE methods have two main drawbacks: 1) sensitive to random scale of training signal and 2) unstable in low signal-to-noise ratio (SNR) regime. To overcome these two harmful factors, in this paper, we propose a novel ASCE method using normalized LMS (NLMS) algorithm (ASCE-NLMS). In addition, we also proposed an improved ASCE method using normalized least mean fourth (NLMF) algorithm (ASCE-NLMF). Two proposed methods can exploit the channel sparsity effectively. Also, stability of the proposed methods is confirmed by mathematical derivation. Computer simulation results show that the proposed sparse channel estimation methods can achieve better estimation performance than conventional methods.
Sparse Channel Estimation for MIMO-OFDM Amplify-and-Forward Two-Way Relay Networks
Guan Gui, Wei Peng, Fumiyuki Adachi
(Submitted on 6 Feb 2013)
Accurate channel impulse response (CIR) is required for coherent detection and it can also help improve communication quality of service in next-generation wireless communication systems. One of the advanced systems is multi-input multi-output orthogonal frequency-division multiplexing (MIMO-OFDM) amplify and forward two-way relay networks (AF-TWRN). Linear channel estimation methods, e.g., least square (LS), have been proposed to estimate the CIR. However, these methods never take advantage of channel sparsity and then cause performance loss. In this paper, we propose a sparse channel estimation method to exploit the sparse structure information in the CIR at each end user. Sparse channel estimation problem is formulated as compressed sensing (CS) using sparse decomposition theory and the estimation process is implemented by LASSO algorithm. Computer simulation results are given to confirm the superiority of proposed method over the LS-based channel estimation method.
Blind One-Bit Compressive Sampling
Lixin Shen, Bruce W. Suter
(Submitted on 6 Feb 2013)
The problem of 1-bit compressive sampling is addressed in this paper. We introduce an optimization model for reconstruction of sparse signals from 1-bit measurements. The model targets a solution that has the least l0-norm among all signals satisfying consistency constraints stemming from the 1-bit measurements. An algorithm for solving the model is developed. Convergence analysis of the algorithm is presented. Our approach is to obtain a sequence of optimization problems by successively approximating the l0-norm and to solve resulting problems by exploiting the proximity operator. We examine the performance of our proposed algorithm and compare it with the binary iterative hard thresholding (BIHT) [10] a state-of-the-art algorithm for 1-bit compressive sampling reconstruction. Unlike the BIHT, our model and algorithm does not require a prior knowledge on the sparsity of the signal. This makes our proposed work a promising practical approach for signal acquisition.
Sparse Camera Network for Visual Surveillance -- A Comprehensive Survey
Mingli Song, Dachent Tao, Stephen J. Maybank
(Submitted on 3 Feb 2013)
Technological advances in sensor manufacture, communication, and computing are stimulating the development of new applications that are transforming traditional vision systems into pervasive intelligent camera networks. The analysis of visual cues in multi-camera networks enables a wide range of applications, from smart home and office automation to large area surveillance and traffic surveillance. While dense camera networks - in which most cameras have large overlapping fields of view - are well studied, we are mainly concerned with sparse camera networks. A sparse camera network undertakes large area surveillance using as few cameras as possible, and most cameras have non-overlapping fields of view with one another. The task is challenging due to the lack of knowledge about the topological structure of the network, variations in the appearance and motion of specific tracking targets in different views, and the difficulties of understanding composite events in the network. In this review paper, we present a comprehensive survey of recent research results to address the problems of intra-camera tracking, topological structure learning, target appearance modeling, and global activity understanding in sparse camera networks. A number of current open research issues are discussed.
Projection Design For Statistical Compressive Sensing: A Tight Frame Based Approach
Wei Chen, Miguel R. D. Rodrigues, Ian Wassell
(Submitted on 4 Feb 2013)
In this paper, we develop a framework to design sensing matrices for compressive sensing applications that lead to good mean squared error (MSE) performance subject to sensing cost constraints. By capitalizing on the MSE of the oracle estimator, whose performance has been shown to act as a benchmark to the performance of standard sparse recovery algorithms, we use the fact that a Parseval tight frame is the closest design - in the Frobenius norm sense - to the solution of a convex relaxation of the optimization problem that relates to the minimization of the MSE of the oracle estimator with respect to the equivalent sensing matrix, subject to sensing energy constraints. Based on this result, we then propose two sensing matrix designs that exhibit two key properties: i) the designs are closed form rather than iterative; ii) the designs exhibit superior performance in relation to other designs in the literature, which is revealed by our numerical investigation in various scenarios with different sparse recovery algorithms including basis pursuit de-noise (BPDN), the Dantzig selector and orthogonal matching pursuit (OMP).
Spread spectrum compressed sensing MRI using chirp radio frequency pulses
Xiaobo Qu, Ying Chen, Xiaoxing Zhuang, Zhiyu Yan, Di Guo, Zhong Chen
(Submitted on 23 Jan 2013)
Compressed sensing has shown great potential in reducing data acquisition time in magnetic resonance imaging (MRI). Recently, a spread spectrum compressed sensing MRI method modulates an image with a quadratic phase. It performs better than the conventional compressed sensing MRI with variable density sampling, since the coherence between the sensing and sparsity bases are reduced. However, spread spectrum in that method is implemented via a shim coil which limits its modulation intensity and is not convenient to operate. In this letter, we propose to apply chirp (linear frequency-swept) radio frequency pulses to easily control the spread spectrum. To accelerate the image reconstruction, an alternating direction algorithm is modified by exploiting the complex orthogonality of the quadratic phase encoding. Reconstruction on the acquired data demonstrates that more image features are preserved using the proposed approach than those of conventional CS-MRI.
Non-Adaptive Distributed Compression in Networks
Mahdy Nabaee, Fabrice Labeau
(Submitted on 25 Jan 2013)
In this paper, we discuss non-adaptive distributed compression of inter-node correlated real-valued messages. To do so, we discuss the performance of conventional packet forwarding via routing, in terms of the total network load versus the resulting quality of service (distortion level). As a better alternative for packet forwarding, we briefly describe our previously proposed one-step Quantized Network Coding (QNC), and make motivating arguments on its advantage when the appropriate marginal rates for distributed source coding are not available at the encoder source nodes. We also derive analytic guarantees on the resulting distortion of our one-step QNC scenario. Finally, we conclude the paper by providing a mathematical comparison between the total network loads of one-step QNC and conventional packet forwarding, showing a significant reduction in the case of one-step QNC.
A Proof of Threshold Saturation for Spatially-Coupled LDPC Codes on BMS Channels
Santhosh Kumar, Andrew J. Young, Nicolas Macris, Henry D. Pfister
(Submitted on 25 Jan 2013)
Low-density parity-check (LDPC) convolutional codes have been shown to exhibit excellent performance under low-complexity belief-propagation decoding [1], [2]. This phenomenon is now termed threshold saturation via spatial coupling. The underlying principle behind this appears to be very general and spatially-coupled (SC) codes have been successfully applied in numerous areas. Recently, SC regular LDPC codes have been proven to achieve capacity universally, over the class of binary memoryless symmetric (BMS) channels, under belief-propagation decoding [3], [4].
In [5], [6], potential functions are used to prove that the BP threshold of SC irregular LDPC ensembles saturates, for the binary erasure channel, to the conjectured MAP threshold (known as the Maxwell threshold) of the underlying irregular ensembles. In this paper, that proof technique is generalized to BMS channels, thereby extending some results of [4] to irregular LDPC ensembles. We also believe that this approach can be expanded to cover a wide class of graphical models whose message-passing rules are associated with a Bethe free energy.
Sample Complexity of Bayesian Optimal Dictionary Learning
Ayaka Sakata, Yoshiyuki Kabashima
(Submitted on 26 Jan 2013)
We consider a learning problem of identifying a dictionary matrix D (M times N dimension) from a sample set of M dimensional vectors Y = N^{-1/2} DX, where X is a sparse matrix (N times P dimension) in which the density of non-zero entries is 0rho is satisfied in the limit of N to infinity. Our analysis also implies that the posterior distribution given Y is condensed only at the correct dictionary D when the compression rate alpha is greater than a certain critical value alpha_M(rho). This suggests that belief propagation may allow us to learn D with a low computational complexity using O(N) samples.
Tight is better: Performance Improvement of the Compressive Classifier Using Equi-Norm Tight Frames
Hailong Shi, Hao Zhang
(Submitted on 26 Jan 2013)
Detecting or classifying already known sparse signals contaminated by Gaussian noise from compressive measurements is different from reconstructing sparse signals, as its objective is to minimize the error probability which describes performance of the detectors or classifiers. This paper is concerned about the performance improvement of a commonly used Compressive Classifier. We prove that when the arbitrary sensing matrices used to get the Compressive Measurements are transformed into Equi-Norm Tight Frames, i.e. the matrices that are row-orthogonal, The Compressive Classifier achieves better performance. Although there are other proofs that among all Equi-Norm Tight Frames the Equiangular tight Frames (ETFs) bring best worst-case performance, the existence and construction of ETFs on some dimensions is still an open problem. As the construction of Equi-Norm Tight Frames from any arbitrary matrices is very easy and practical compared with ETF matrices, the result of this paper can also provide a practical method to design an improved sensing matrix for Compressive Classification. We can conclude that: Tight is Better!
Linear Programming Decoding of Spatially Coupled Codes
Louay Bazzi, Badih Ghazi, Rudiger Urbanke
(Submitted on 27 Jan 2013 (v1), last revised 5 Mar 2013 (this version, v2))
For a given family of spatially coupled codes, we prove that the LP threshold on the BSC of the graph cover ensemble is the same as the LP threshold on the BSC of the derived spatially coupled ensemble. This result is in contrast with the fact that the BP threshold of the derived spatially coupled ensemble is believed to be larger than the BP threshold of the graph cover ensemble as noted by the work of Kudekar et al. (2011, 2012). To prove this, we establish some properties related to the dual witness for LP decoding which was introduced by Feldman et al. (2007) and simplified by Daskalakis et al. (2008). More precisely, we prove that the existence of a dual witness which was previously known to be sufficient for LP decoding success is also necessary and is equivalent to the existence of certain acyclic hyperflows. We also derive a sublinear (in the block length) upper bound on the weight of any edge in such hyperflows, both for regular LPDC codes and for spatially coupled codes and we prove that the bound is asymptotically tight for regular LDPC codes. Moreover, we show how to trade crossover probability for "LP excess" on all the variable nodes, for any binary linear code.
Guarantees of Total Variation Minimization for Signal Recovery
Jian-Feng Cai, Weiyu Xu
(Submitted on 28 Jan 2013)
In this paper, we consider using total variation minimization to recover signals whose gradients have a sparse support, from a small number of measurements. We establish the proof for the performance guarantee of total variation (TV) minimization in recovering \emph{one-dimensional} signal with sparse gradient support. This partially answers the open problem of proving the fidelity of total variation minimization in such a setting \cite{TVMulti}. We also extend our results to TV minimization for multidimensional signals. Recoverable sparsity thresholds of TV minimization are explicitly computed for 1-dimensional signal by using the Grassmann angle framework.
Robust Face Recognition via Block Sparse Bayesian Learning
Taiyong Li, Zhilin Zhang
(Submitted on 29 Jan 2013)
Face recognition (FR) is an important task in pattern recognition and computer vision. Sparse representation (SR) has been demonstrated to be a powerful framework for FR. In general, an SR algorithm treats each face in a training dataset as a basis function, and tries to find a sparse representation of a test face under these basis functions. The sparse representation coefficients then provide a recognition hint. Early SR algorithms are based on a basic sparse model. Recently, it is found that algorithms based on a block sparse model can achieve better recognition rates. Based on this model, in this paper we use block sparse Bayesian learning (BSBL) to find a sparse representation of a test face for recognition. BSBL is a recently proposed framework, which has many advantages over existing block-sparse-model based algorithms. Experimental results on the Extended Yale B and the AR face database show that using BSBL can achieve better recognition rates and higher robustness than state-of-the-art algorithms in most cases.
Spatial degrees of freedom of MIMO systems in Line-of-Sight Environment
Marc Desgroseilliers, Olivier Leveque, Emmanuel Preissmann
(Submitted on 30 Jan 2013)
While the efficiency of MIMO transmissions in a rich scattering environment has been demonstrated, less is known about the situation where the fading matrix coefficients come from a line-of-sight model. In this paper, we study in detail how this line-of-sight assumption affects the performance of distributed MIMO transmissions between far away clusters of nodes in a wireless network. Our analysis pertains to the study of a new class of random matrices.
The varying w spread spectrum effect for radio interferometric imaging
Laura Wolz, Filipe B. Abdalla, Rafael E. Carrillo, Yves Wiaux, Jason D. McEwen
(Submitted on 30 Jan 2013)
We study the impact of the spread spectrum effect in radio interferometry on the quality of image reconstruction. This spread spectrum effect will be induced by the wide field-of-view of forthcoming radio interferometric telescopes. The resulting chirp modulation improves the quality of reconstructed interferometric images by increasing the incoherence of the measurement and sparsity dictionaries. We extend previous studies of this effect to consider the more realistic setting where the chirp modulation varies for each visibility measurement made by the telescope. In these first preliminary results, we show that for this setting the quality of reconstruction improves significantly over the case without chirp modulation and achieves almost the reconstruction quality of the case of maximal, constant chirp modulation.
Load curve data cleansing and imputation via sparsity and low rank
Gonzalo Mateos, Georgios B. Giannakis
(Submitted on 31 Jan 2013)
The smart grid vision is to build an intelligent power network with an unprecedented level of situational awareness and controllability over its services and infrastructure. This paper advocates statistical inference methods to robustify power monitoring tasks against the outlier effects owing to faulty readings and malicious attacks, as well as against missing data due to privacy concerns and communication errors. In this context, a novel load cleansing and imputation scheme is developed leveraging the low intrinsic-dimensionality of spatiotemporal load profiles and the sparse nature of "bad data.'' A robust estimator based on principal components pursuit (PCP) is adopted, which effects a twofold sparsity-promoting regularization through an $\ell_1$-norm of the outliers, and the nuclear norm of the nominal load profiles. Upon recasting the non-separable nuclear norm into a form amenable to decentralized optimization, a distributed (D-) PCP algorithm is developed to carry out the imputation and cleansing tasks using networked devices comprising the so-termed advanced metering infrastructure. If D-PCP converges and a qualification inequality is satisfied, the novel distributed estimator provably attains the performance of its centralized PCP counterpart, which has access to all networkwide data. Computer simulations and tests with real load curve data corroborate the convergence and effectiveness of the novel D-PCP algorithm.
Sparse MRI for motion correction
Zai Yang, Cishen Zhang, Lihua Xie
(Submitted on 1 Feb 2013)
MR image sparsity/compressibility has been widely exploited for imaging acceleration with the development of compressed sensing. A sparsity-based approach to rigid-body motion correction is presented for the first time in this paper. A motion is sought after such that the compensated MR image is maximally sparse/compressible among the infinite candidates. Iterative algorithms are proposed that jointly estimate the motion and the image content. The proposed method has a lot of merits, such as no need of additional data and loose requirement for the sampling sequence. Promising results are presented to demonstrate its performance.
Robust Compressive Phase Retrieval via L1 Minimization With Application to Image Reconstruction
Zai Yang, Cishen Zhang, Lihua Xie
(Submitted on 1 Feb 2013)
Phase retrieval refers to a classical nonconvex problem of recovering a signal from its Fourier magnitude measurements. Inspired by the compressed sensing technique, signal sparsity is exploited in recent studies of phase retrieval to reduce the required number of measurements, known as compressive phase retrieval (CPR). In this paper, l1 minimization problems are formulated for CPR to exploit the signal sparsity and alternating direction algorithms are presented for problem solving. For real-valued, nonnegative image reconstruction, the image of interest is shown to be an optimal solution of the formulated l1 minimization in the noise free case. Numerical simulations demonstrate that the proposed approach is fast, accurate and robust to measurements noises.
Revisiting the Nystrom Method for Improved Large-Scale Machine Learning
Alex Gittens, Michael W. Mahoney
(Submitted on 7 Mar 2013)
We reconsider randomized algorithms for the low-rank approximation of symmetric positive semi-definite (SPSD) matrices such as Laplacian and kernel matrices that arise in data analysis and machine learning applications. Our main results consist of an empirical evaluation of the performance quality and running time of sampling and projection methods on a diverse suite of SPSD matrices. Our results highlight complementary aspects of sampling versus projection methods based on leverage scores. We complement our empirical results with a suite of worst-case theoretical bounds for both random sampling and random projections methods. These bounds are qualitatively superior to existing bounds---e.g., improved additive-error bounds for the spectral and Frobenius norm errors and relative-error bounds for the trace norm error.
Adaptive Low-rank Constrained Constant Modulus Beamforming Algorithms using Joint Iterative Optimization of Parameters
Lei Wang, Rodrigo C. de Lamare
(Submitted on 14 Mar 2013)
This paper proposes a robust reduced-rank scheme for adaptive beamforming based on joint iterative optimization (JIO) of adaptive filters. The scheme provides an efficient way to deal with filters with large number of elements. It consists of a bank of full-rank adaptive filters that forms a transformation matrix and an adaptive reduced-rank filter that operates at the output of the bank of filters. The transformation matrix projects the received vector onto a low-dimension vector, which is processed by the reduced-rank filter to estimate the desired signal. The expressions of the transformation matrix and the reduced-rank weight vector are derived according to the constrained constant modulus (CCM) criterion. Two novel low-complexity adaptive algorithms are devised for the implementation of the proposed scheme with respect to different constrained conditions. Simulations are performed to show superior performance of the proposed algorithms in comparison with the existing methods.
Real and complex rank for real symmetric tensors with low ranks
Edoardo Ballico, Alessandra Bernardi
(Submitted on 11 Mar 2013)
We study the case of a real homogeneous polynomial $P$ whose minimal real and complex decompositions in terms of powers of linear forms are different. We prove that, if the sum of the complex and the real ranks of $P$ is at most $ 3\deg(P)-1$, then the difference of the two decompositions is completely determined either on a line or on a conic or two disjoint lines.
On the Coherence Properties of Random Euclidean Distance Matrices
Dionysios Kalogerias, Athina Petropulu
(Submitted on 4 Mar 2013)
In the present paper we focus on the coherence properties of general random Euclidean distance matrices, which are very closely related to the respective matrix completion problem. This problem is of great interest in several applications such as node localization in sensor networks with limited connectivity. Our results can directly provide the sufficient conditions under which an EDM can be successfully recovered with high probability from a limited number of measurements.
Sparse PCA through Low-rank Approximations
Dimitris S. Papailiopoulos, Alexandros G. Dimakis, Stavros Korokythakis
(Submitted on 3 Mar 2013)
We introduce a novel algorithm that computes the $k$-sparse principal component of a positive semidefinite matrix $A$. Our algorithm is combinatorial and operates by examining a discrete set of special vectors lying in a low-dimensional eigen-subspace of $A$. We obtain provable approximation guarantees that depend on the spectral profile of the matrix: the faster the eigenvalue decay, the better the quality of our approximation. For example, if the eigenvalues of $A$ follow a power-law decay, we obtain a polynomial-time approximation algorithm for any desired accuracy. We implement our algorithm and test it on multiple artificial and real data sets. Due to a feature elimination step, it is possible to perform sparse PCA on data sets consisting of millions of entries in a few minutes. Our experimental evaluation shows that our scheme is nearly optimal while finding very sparse vectors. We compare to the prior state of the art and show that our scheme matches or outperforms previous algorithms in all tested data sets.
Matrix completion via max-norm constrained optimization
T. Tony Cai, Wenxin Zhou
(Submitted on 2 Mar 2013)
This paper studies matrix completion under a general sampling model using the max-norm as a convex relaxation for the rank of the matrix. The optimal rate of convergence is established for the Frobenius norm loss. It is shown that the max-norm constrained minimization method is rate-optimal and it yields a more stable approximate recovery guarantee, with respect to the sampling distributions, than previously used trace-norm based approaches. The computational effectiveness of this method is also studied, based on a first-order algorithm for solving convex programs involving a max-norm constraint.
Source Separation using Regularized NMF with MMSE Estimates under GMM Priors with Online Learning for The Uncertainties
Emad M. Grais, Hakan Erdogan
(Submitted on 28 Feb 2013)
We propose a new method to enforce priors on the solution of the nonnegative matrix factorization (NMF). The proposed algorithm can be used for denoising or single-channel source separation (SCSS) applications. The NMF solution is guided to follow the Minimum Mean Square Error (MMSE) estimates under Gaussian mixture prior models (GMM) for the source signal. In SCSS applications, the spectra of the observed mixed signal are decomposed as a weighted linear combination of trained basis vectors for each source using NMF. In this work, the NMF decomposition weight matrices are treated as a distorted image by a distortion operator, which is learned directly from the observed signals. The MMSE estimate of the weights matrix under GMM prior and log-normal distribution for the distortion is then found to improve the NMF decomposition results. The MMSE estimate is embedded within the optimization objective to form a novel regularized NMF cost function. The corresponding update rules for the new objectives are derived in this paper. Experimental results show that, the proposed regularized NMF algorithm improves the source separation performance compared with using NMF without prior or with other prior models.
A literature survey of low-rank tensor approximation techniques
Lars Grasedyck, Daniel Kressner, Christine Tobler
(Submitted on 28 Feb 2013)
During the last years, low-rank tensor approximation has been established as a new tool in scientific computing to address large-scale linear and multilinear algebra problems, which would be intractable by classical techniques. This survey attempts to give a literature overview of current developments in this area, with an emphasis on function-related tensors.
Scoup-SMT: Scalable Coupled Sparse Matrix-Tensor Factorization
Evangelos E. Papalexakis, Tom M. Mitchell, Nicholas D. Sidiropoulos,Christos Faloutsos, Partha Pratim Talukdar, Brian Murphy
(Submitted on 28 Feb 2013)
How can we correlate neural activity in the human brain as it responds to words, with behavioral data expressed as answers to questions about these same words? In short, we want to find latent variables, that explain both the brain activity, as well as the behavioral responses. We show that this is an instance of the Coupled Matrix-Tensor Factorization (CMTF) problem. We propose Scoup-SMT, a novel, fast, and parallel algorithm that solves the CMTF problem and produces a sparse latent low-rank subspace of the data. In our experiments, we find that Scoup-SMT is 50-100 times faster than a state-of-the-art algorithm for CMTF, along with a 5 fold increase in sparsity. Moreover, we extend Scoup-SMT to handle missing data without degradation of performance. We apply Scoup-SMT to BrainQ, a dataset consisting of a (nouns, brain voxels, human subjects) tensor and a (nouns, properties) matrix, with coupling along the nouns dimension. Scoup-SMT is able to find meaningful latent variables, as well as to predict brain activity with competitive accuracy. Finally, we demonstrate the generality of Scoup-SMT, by applying it on a Facebook dataset (users, friends, wall-postings); there, Scoup-SMT spots spammer-like anomalies.
Missing Entries Matrix Approximation and Completion
Gil Shabat, Yaniv Shmueli, Amir Averbuch
(Submitted on 27 Feb 2013)
We describe several algorithms for matrix completion and matrix approximation when only some of its entries are known. The approximation constraint can be any whose approximated solution is known for the full matrix. For low rank approximations, similar algorithms appears recently in the literature under different names. In this work, we introduce new theorems for matrix approximation and show that these algorithms can be extended to handle different constraints such as nuclear norm, spectral norm, orthogonality constraints and more that are different than low rank approximations. As the algorithms can be viewed from an optimization point of view, we discuss their convergence to global solution for the convex case. We also discuss the optimal step size and show that it is fixed in each iteration. In addition, the derived matrix completion flow is robust and does not require any parameters. This matrix completion flow is applicable to different spectral minimizations and can be applied to physics, mathematics and electrical engineering problems such as data reconstruction of images and data coming from PDEs such as Helmholtz equation used for electromagnetic waves.
An SVD-free Pareto curve approach to rank minimization
Aleksandr Y. Aravkin, Rajiv Mittal, Hassan Mansour, Ben Recht, Felix J. Herrmann
(Submitted on 20 Feb 2013)
Recent SVD-free matrix factorization formulations have enabled rank optimization for extremely large-scale systems (millions of rows and columns). In this paper, we consider rank-regularized formulations that only require a target data-fitting error level, and propose an algorithm for the corresponding problem. We illustrate the advantages of the new approach using the Netflix prob- lem, and use it to obtain high quality results for seismic trace interpolation, a key application in exploration geophysics. We show that factor rank can be easily adjusted as the inversion proceeds, and propose a weighted extension that allows known subspace information to improve the results of matrix completion formulations. Using these methods, we obtain high-quality reconstructions for large scale seismic interpolation problems with real data.
Target Estimation in Colocated MIMO Radar via Matrix Completion
Shunqiao Sun, Athina P. Petropulu, Waheed U. Bajwa
(Submitted on 17 Feb 2013)
We consider a colocated MIMO radar scenario, in which the receive antennas forward their measurements to a fusion center. Based on the received data, the fusion center formulates a matrix which is then used for target parameter estimation. When the receive antennas sample the target returns at Nyquist rate, and assuming that there are more receive antennas than targets, the data matrix at the fusion center is low-rank. When each receive antenna sends to the fusion center only a small number of samples, along with the sample index, the receive data matrix has missing elements, corresponding to the samples that were not forwarded. Under certain conditions, matrix completion techniques can be applied to recover the full receive data matrix, which can then be used in conjunction with array processing techniques, e.g., MUSIC, to obtain target information. Numerical results indicate that good target recovery can be achieved with occupancy of the receive data matrix as low as 50%.
An Efficient Implementation of the Ensemble Kalman Filter Based on an Iterative Sherman-Morrison Formula
Elias D. Nino-Ruiz, Adrian Sandu, Jeffrey Anderson
(Submitted on 15 Feb 2013)
We present a practical implementation of the ensemble Kalman (EnKF) filter based on an iterative Sherman-Morrison formula. The new direct method exploits the special structure of the ensemble-estimated error covariance matrices in order to efficiently solve the linear systems involved in the analysis step of the EnKF. The computational complexity of the proposed implementation is equivalent to that of the best EnKF implementations available in the literature when the number of observations is much larger than the number of ensemble members. Even when this conditions is not fulfilled, the proposed method is expected to perform well since it does not employ matrix decompositions. Computational experiments using the Lorenz 96 and the oceanic quasi-geostrophic models are performed in order to compare the proposed algorithm with EnKF implementations that use matrix decompositions. In terms of accuracy, the results of all implementations are similar. The proposed method is considerably faster than other EnKF variants, even when the number of observations is large relative to the number of ensemble members.
Baselining Network-Wide Traffic by Time-Frequency Constrained Stable Principal Component Pursuit
Kai Hu, Zhe Wang
(Submitted on 14 Feb 2013 (v1), last revised 27 Feb 2013 (this version, v2))
In this letter, we develop a novel network-wide traffic analysis methodology, named Stable Principal Component Pursuit with Time-Frequency Constraints (SPCP-TFC), for extracting the baseline of a traffic matrix. Following a refined traffic matrix decomposition model, we present new time-frequency constraints to extend Stable Principal Component Pursuit (SPCP), and design an efficient numerical algorithm for SPCP-TFC. At last, we evaluate the SPCP-TFC method by abundant simulations, and show it has a superior performance than other traffic baseline methods such as RBL and PCA.
Covariance Estimation in High Dimensions via Kronecker Product Expansions
Theodoros Tsiligkaridis, Alfred O. Hero III
(Submitted on 12 Feb 2013 (v1), last revised 28 Feb 2013 (this version, v3))
This paper presents a new method for estimating high dimensional covariance matrices. Our method, permuted rank-penalized least-squares (PRLS), is based on a Kronecker product series expansion of the true covariance matrix. Assuming an i.i.d. Gaussian random sample, we establish high dimensional rates of convergence to the true covariance as both the number of samples and the number of variables go to infinity. For covariance matrices of low separation rank, our results establish that PRLS has significantly faster convergence than the standard sample covariance matrix (SCM) estimator. In addition, this framework captures a fundamental tradeoff between estimation error and approximation error, thus providing a scalable covariance estimation framework in terms of separation rank, an analog to low rank approximation of covariance matrices. The MSE convergence rates generalize the high dimensional rates recently obtained for the ML Flip-flop algorithm for Kronecker product covariance estimation. We show that a class of block Toeplitz covariance matrices has low separation rank and give bounds on the minimal separation rank $r$ that ensures a given level of bias. Simulations are presented to validate the theoretical bounds. As a real world application, we illustrate the utility of the proposed Kronecker covariance estimator in spatio-temporal linear least squares prediction of multivariate wind speed measurements.
Matrix Completion and Tensor Rank
Harm Derksen
(Submitted on 11 Feb 2013)
In this paper, we show that the low rank matrix completion problem can be reduced to the problem of finding the rank of a certain tensor.
Adaptive Space-Time Beamforming in Radar Systems
Rodrigo C. de Lamare
(Submitted on 10 Feb 2013)
The goal of this chapter is to review the recent work and advances in the area of space-time beamforming algorithms and their application to radar systems. These systems include phased-array \cite{melvin} and multi-input multi-output (MIMO) radar systems \cite{haimo_08}, mono-static and bi-static radar systems and other configurations \cite{melvin}. Furthermore, this chapter also describes in detail some of the most successful space-time beamforming algorithms that exploit low-rank and sparsity properties as well as the use of prior-knowledge to improve the performance of STAP algorithms in radar systems.
The Phase Transition of Matrix Recovery from Gaussian Measurements Matches the Minimax MSE of Matrix Denoising
David L. Donoho, Matan Gavish, Andrea Montanari
(Submitted on 10 Feb 2013)
Let $X_0$ be an unknown $M$ by $N$ matrix. In matrix recovery, one takes $n < MN$ linear measurements $y_1,..., y_n$ of $X_0$, where $y_i = \Tr(a_i^T X_0)$ and each $a_i$ is a $M$ by $N$ matrix. For measurement matrices with Gaussian i.i.d entries, it known that if $X_0$ is of low rank, it is recoverable from just a few measurements. A popular approach for matrix recovery is Nuclear Norm Minimization (NNM). Empirical work reveals a \emph{phase transition} curve, stated in terms of the undersampling fraction $\delta(n,M,N) = n/(MN)$, rank fraction $\rho=r/N$ and aspect ratio $\beta=M/N$. Specifically, a curve $\delta^* = \delta^*(\rho;\beta)$ exists such that, if $\delta > \delta^*(\rho;\beta)$, NNM typically succeeds, while if $\delta < \delta^*(\rho;\beta)$, it typically fails. An apparently quite different problem is matrix denoising in Gaussian noise, where an unknown $M$ by $N$ matrix $X_0$ is to be estimated based on direct noisy measurements $Y = X_0 + Z$, where the matrix $Z$ has iid Gaussian entries. It has been empirically observed that, if $X_0$ has low rank, it may be recovered quite accurately from the noisy measurement $Y$. A popular matrix denoising scheme solves the unconstrained optimization problem $\text{min} \| Y - X \|_F^2/2 + \lambda \|X\|_* $. When optimally tuned, this scheme achieves the asymptotic minimax MSE $\cM(\rho) = \lim_{N \goto \infty} \inf_\lambda \sup_{\rank(X) \leq \rho \cdot N} MSE(X,\hat{X}_\lambda)$. We report extensive experiments showing that the phase transition $\delta^*(\rho)$ in the first problem coincides with the minimax risk curve $\cM(\rho)$ in the second problem, for {\em any} rank fraction $0 < \rho < 1$.
Efficient Data Gathering in Wireless Sensor Networks Based on Matrix Completion and Compressive Sensing
Jiping Xiong, Jian Zhao, Lei Chen
(Submitted on 9 Feb 2013)
Gathering data in an energy efficient manner in wireless sensor networks is an important design challenge. In wireless sensor networks, the readings of sensors always exhibit intra-temporal and inter-spatial correlations. Therefore, in this letter, we use low rank matrix completion theory to explore the inter-spatial correlation and use compressive sensing theory to take advantage of intra-temporal correlation. Our method, dubbed MCCS, can significantly reduce the amount of data that each sensor must send through network and to the sink, thus prolong the lifetime of the whole networks. Experiments using real datasets demonstrate the feasibility and efficacy of our MCCS method.
pROST : A Smoothed Lp-norm Robust Online Subspace Tracking Method for Realtime Background Subtraction in Video
Florian Seidel, Clemens Hage, Martin Kleinsteuber
(Submitted on 8 Feb 2013)
An increasing number of methods for background subtraction use Robust PCA to identify sparse foreground objects. While many algorithms use the L1-norm as a convex relaxation of the ideal sparsifying function, we approach the problem with a smoothed Lp-norm and present pROST, a method for robust online subspace tracking. The algorithm is based on alternating minimization on manifolds. Implemented on a graphics processing unit it achieves realtime performance. Experimental results on a state-of-the-art benchmark for background subtraction on real-world video data indicate that the method succeeds at a broad variety of background subtraction scenarios, and it outperforms competing approaches when video quality is deteriorated by camera jitter.
Surveillance Video Processing Using Compressive Sensing
Hong Jiang, Wei Deng, Zuowei Shen
(Submitted on 8 Feb 2013)
A compressive sensing method combined with decomposition of a matrix formed with image frames of a surveillance video into low rank and sparse matrices is proposed to segment the background and extract moving objects in a surveillance video. The video is acquired by compressive measurements, and the measurements are used to reconstruct the video by a low rank and sparse decomposition of matrix. The low rank component represents the background, and the sparse component is used to identify moving objects in the surveillance video. The decomposition is performed by an augmented Lagrangian alternating direction method. Experiments are carried out to demonstrate that moving objects can be reliably extracted with a small amount of measurements.
Correcting beliefs in the mean-field and Bethe approximations using linear response
Jack Raymond, Federico Ricci-Tersenghi
(Submitted on 7 Feb 2013)
Approximating marginals of a graphical model is one of the fundamental problems in the theory of networks. In a recent paper a method was shown to construct a variational free energy such that the linear response estimates, and maximum entropy estimates (for beliefs) are in agreement, with implications for direct and inverse Ising problems[1]. In this paper we demonstrate an extension of that method, incorporating new information from the response matrix, and we recover the adaptive-TAP equations as the first order approximation[2]. The method is flexible with respect to applications of the cluster variational method, special cases of this method include Naive Mean Field (NMF) and Bethe. We demonstrate that the new framework improves estimation of marginals by orders of magnitude over standard implementations in the weak coupling limit. Beyond the weakly coupled regime we show there is an improvement in a model where the NMF and Bethe approximations are known to be poor for reasons of frustration and short loops.
Adaptive low rank and sparse decomposition of video using compressive sensing
Fei Yang, Hong Jiang, Zuowei Shen, Wei Deng, Dimitris Metaxas
(Submitted on 6 Feb 2013)
We address the problem of reconstructing and analyzing surveillance videos using compressive sensing. We develop a new method that performs video reconstruction by low rank and sparse decomposition adaptively. Background subtraction becomes part of the reconstruction. In our method, a background model is used in which the background is learned adaptively as the compressive measurements are processed. The adaptive method has low latency, and is more robust than previous methods. We will present experimental results to demonstrate the advantages of the proposed method.
Regularised PCA to denoise and visualise data
Marie Verbanck, Julie Josse, François Husson
(Submitted on 20 Jan 2013)
Principal component analysis (PCA) is a well-established method commonly used to explore and visualise data. A classical PCA model is the fixed effect model where data are generated as a fixed structure of low rank corrupted by noise. Under this model, PCA does not provide the best recovery of the underlying signal in terms of mean squared error. Following the same principle as in ridge regression, we propose a regularised version of PCA that boils down to threshold the singular values. Each singular value is multiplied by a term which can be seen as the ratio of the signal variance over the total variance of the associated dimension. The regularised term is analytically derived using asymptotic results and can also be justified from a Bayesian treatment of the model. Regularised PCA provides promising results in terms of the recovery of the true signal and the graphical outputs in comparison with classical PCA and with a soft thresholding estimation strategy. The gap between PCA and regularised PCA is all the more important that data are noisy.
Model-based scaling and prediction of the streamwise energy intensity in high-Reynolds number turbulent channels
Rashad Moarref, Ati S. Sharma, Joel A. Tropp, Beverley J. McKeon
(Submitted on 6 Feb 2013)
We study the Reynolds number scaling of a gain-based, low-rank approximation to turbulent channel flows, determined by the resolvent formulation of McKeon & Sharma (2010), in order to obtain a description of the streamwise turbulence intensity from direct consideration of the Navier-Stokes equations. Under this formulation, the velocity field is decomposed into propagating waves (with single streamwise and spanwise wavelengths and wave speed) whose wall-normal shapes are determined from the principal singular function of the corresponding resolvent operator. We establish that the resolvent formulation admits three classes of wave parameters that induce universal behavior with Reynolds number on the low-rank model, and which are consistent with scalings proposed throughout the wall turbulence literature. For the rank-1 model subject to broadband forcing, the integrated streamwise energy density takes a universal form which is consistent with the dominant near-wall turbulent motions. When the shape of the forcing is optimized to enforce matching with results from direct numerical simulations at low turbulent Reynolds numbers, further similarity appears. Representation of these weight functions using similarity laws enables prediction of the Reynolds number and wall-normal variations of the streamwise energy intensity at high Reynolds numbers (${Re}_\tau \approx 10^3 - 10^{10}$). Results from this low rank model of the Navier-Stokes equations compare favorably with experimental results in the literature.
Hierarchical Data Representation Model - Multi-layer NMF
Hyun Ah Song, Soo-Young Lee
(Submitted on 27 Jan 2013 (v1), last revised 14 Mar 2013 (this version, v2))
In this paper, we propose a data representation model that demonstrates hierarchical feature learning using nsNMF. We extend unit algorithm into several layers to take step-by-step approach in learning. Experiments with document and image data successfully demonstrated feature hierarchies. In addition, we showed that taking hierarchical steps also guarantees learning of more meaningful features which leads to better distributed representations, and improved performance in classification and reconstruction tasks, which supports benefits of further application of our proposed data representation model.
Model-based scaling and prediction of the streamwise energy intensity in high-Reynolds number turbulent channels
Rashad Moarref, Ati S. Sharma, Joel A. Tropp, Beverley J. McKeon
(Submitted on 6 Feb 2013)
We study the Reynolds number scaling of a gain-based, low-rank approximation to turbulent channel flows, determined by the resolvent formulation of McKeon & Sharma (2010), in order to obtain a description of the streamwise turbulence intensity from direct consideration of the Navier-Stokes equations. Under this formulation, the velocity field is decomposed into propagating waves (with single streamwise and spanwise wavelengths and wave speed) whose wall-normal shapes are determined from the principal singular function of the corresponding resolvent operator. We establish that the resolvent formulation admits three classes of wave parameters that induce universal behavior with Reynolds number on the low-rank model, and which are consistent with scalings proposed throughout the wall turbulence literature. For the rank-1 model subject to broadband forcing, the integrated streamwise energy density takes a universal form which is consistent with the dominant near-wall turbulent motions. When the shape of the forcing is optimized to enforce matching with results from direct numerical simulations at low turbulent Reynolds numbers, further similarity appears. Representation of these weight functions using similarity laws enables prediction of the Reynolds number and wall-normal variations of the streamwise energy intensity at high Reynolds numbers (${Re}_\tau \approx 10^3 - 10^{10}$). Results from this low rank model of the Navier-Stokes equations compare favorably with experimental results in the literature.
Image Credit: NASA/JPL-Caltech
This image was taken by Front Hazcam: Right B (FHAZ_RIGHT_B) onboard NASA's Mars rover Curiosity on Sol 235 (2013-04-04 10:54:26 UTC).
Full Resolution
Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.
No comments:
Post a Comment