We study the underlying structure of data (approximately) generated from a union of independent subspaces. Traditional methods learn only one subspace, failing to discover the multi-subspace structure, while state-of-the-art methods analyze the multi-subspace structure using data themselves as the dictionary, which cannot offer the explicit basis to span each subspace and are sensitive to errors via an indirect representation. Additionally, they also suffer from a high computational complexity, being quadratic or cubic to the sample size. To tackle all these problems, we propose a method, called Matrix Factorization with Column L0-norm constraint (MFC0), that can simultaneously learn the basis for each subspace, generate a direct sparse representation for each data sample, as well as removing errors in the data in an efficient way. Furthermore, we develop a first-order alternating direction algorithm, whose computational complexity is linear to the sample size, to stably and effectively solve the nonconvex objective function and non- smooth l0-norm constraint of MFC0. Experimental results on both synthetic and real-world datasets demonstrate that besides the superiority over traditional and state-of-the-art methods for subspace clustering, data reconstruction, error correction, MFC0 also shows its uniqueness for multi-subspace basis learning and direct sparse representation.
@math -norm based sparsity Little work has been done using direct @math -norm, the exact sparsity measure which causes the NP-hard combinational optimization problem. K-SVD @cite_19 aims to find an overcomplete dictionary for sparse representation, and the sparse approximation is based on an @math -norm inequality constraint and is solved via greedy orthogonal matching pursuit (OMP) @cite_7 . Peharz and Pernkopf @cite_43 further proposed sparse NMF that introduced an @math -norm to constrain the basis or representation matrix of approximate NMF. It is solved via sparse alternating nonnegative least-squares (sANLS). @cite_47 leveraged hierarchical Bayes to model an adaptive sparseness prior, which has a similar properity with an @math -norm. However, these methods are under the hidden assumption that data are generated from single subspace. In addition, they cannot handle various errors. In this work, we focus on analyzing data (approximately) drawn from multiple subspaces. Different from using greedy methods, the @math -norm constraint in MFC @math is solved analytically via our designed proximal operator, which is easy to be incorporated into our developed alternating direction algorithm.
@cite_19 @cite_47 @cite_43 @cite_7
2127300249 2170293972 2083945855 2106460483
The problem of consistently estimating the sparsity pattern of a vector β* ∈ RP based on observations contaminated by noise arises in various contexts, including signal denoising, sparse approximation, compressed sensing, and model selection. We analyze the behavior of l1-constrained quadratic programming (QP), also referred to as the Lasso, for recovering the sparsity pattern. Our main result is to establish precise conditions on the problern dimension p, the number k of nonzero elements in β*, and the number of observations n that are necessary and sufficient for sparsity pattern recovery using the Lasso. We first analyze the case of observations made using deterministic design matrices and sub-Gaussian additive noise, and provide sufficient conditions for support recovery and l∞-error bounds, as well as results showing the necessity of incoherence and bounds on the minimum value. We then turn to the case of random designs, in which each row of the design is drawn from a N(0, Σ) ensemble. For a broad class of Gaussian ensembles satisfying mutual incoherence conditions, we compute explicit values of thresholds 0 0, if n > 2(θu + δ)k log(p - k), then the Lasso succeeds in recovering the sparsity pattern with probability converging to one for large problems, whereas for n < 2(θl - δ)k log(p - k), then the probability of successful recovery converges to zero. For the special case of the uniform Gaussian ensemble (Σ = I p×p), we show that θl = θu = 1, so that the precise threshold n = 2k log (p - k) is exactly determined. Non-negative matrix factorization (NMF), i.e. V ap WH where both V, W and H are non-negative has become a widely used blind source separation technique due to its part based representation. The NMF decomposition is not in general unique and a part based representation not guaranteed. However, imposing sparseness both improves the uniqueness of the decomposition and favors part based representation. Sparseness in the form of attaining as many zero elements in the solution as possible is appealing from a conceptional point of view and corresponds to minimizing reconstruction error with an L0 norm constraint. In general, solving for a given L0 norm is an NP hard problem thus convex relaxation to regularization by the L1 norm is often considered, i.e., minimizing (1 2||V - WH||F 2 + lambda||H||1).An open problem is to control the degree of sparsity lambda imposed. We here demonstrate that a full regularization path for the L1 norm regularized least squares NMF for fixed W can be calculated at the cost of an ordinary least squares solution based on a modification of the least angle regression and selection (LARS) algorithm forming a non-negativity constrained LARS (NLARS). With the full regularization path, the L1 regularization strength lambda that best approximates a given L0 can be directly accessed and in effect used to control the sparsity of H. The MATLAB code for the NLARS algorithm is available for download. Abstract We investigate the recovery of almost s -sparse vectors x ∈ C N from undersampled and inaccurate data y = A x + e ∈ C m by means of minimizing ‖ z ‖ 1 subject to the equality constraints A z = y . If m ≍ s ln ( N s ) and if Gaussian random matrices A ∈ R m × N are used, this equality-constrained l 1 -minimization is known to be stable with respect to sparsity defects and robust with respect to measurement errors. If m ≍ s ln ( N s ) and if Weibull random matrices are used, we prove here that the equality-constrained l 1 -minimization remains stable and robust. The arguments are based on two key ingredients, namely the robust null space property and the quotient property. The robust null space property relies on a variant of the classical restricted isometry property where the inner norm is replaced by the l 1 -norm and the outer norm is replaced by a norm comparable to the l 2 -norm. For the l 1 -minimization subject to inequality constraints, this yields stability and robustness results that are also valid when considering sparsity relative to a redundant dictionary. As for the quotient property, it relies on lower estimates for the tail probability of sums of independent Weibull random variables. This paper considers the problem of sparse signal recovery when the decoder has prior information on the sparsity pattern of the data. The data vector x=[x1,...,xN]T has a randomly generated sparsity pattern, where the i-th entry is non-zero with probability pi. Given knowledge of these probabilities, the decoder attempts to recover x based on M random noisy projections. Information-theoretic limits on the number of measurements needed to recover the support set of x perfectly are given, and it is shown that significantly fewer measurements can be used if the prior distribution is sufficiently non-uniform. Furthermore, extensions of Basis Pursuit, LASSO, and Orthogonal Matching Pursuit which exploit the prior information are presented. The improved performance of these methods over their standard counterparts is demonstrated using simulations.