We propose two practical non-convex approaches for learning near-isometric, linear embeddings of finite sets of data points. Given a set of training points @math , we consider the secant set @math that consists of all pairwise difference vectors of @math , normalized to lie on the unit sphere. The problem can be formulated as finding a symmetric and positive semi-definite matrix @math that preserves the norms of all the vectors in @math up to a distortion parameter @math . Motivated by non-negative matrix factorization, we reformulate our problem into a Frobenius norm minimization problem, which is solved by the Alternating Direction Method of Multipliers (ADMM) and develop an algorithm, FroMax. Another method solves for a projection matrix @math by minimizing the restricted isometry property (RIP) directly over the set of symmetric, postive semi-definite matrices. Applying ADMM and a Moreau decomposition on a proximal mapping, we develop another algorithm, NILE-Pro, for dimensionality reduction. FroMax is shown to converge faster for smaller @math while NILE-Pro converges faster for larger @math . Both non-convex approaches are then empirically demonstrated to be more computationally efficient than prior convex approaches for a number of applications in machine learning and signal processing.
Using the geometric structure of the data, Hegde, et. al. developed a new deterministic approach, NuMax, to construct a near-isometric, linear embedding @cite_17 . Given a training set @math , the is constructed by taking all pairwise difference vectors of @math , which are then normalized to lie on the unit sphere. Hegde, et. al. formulated a rank minimization problem with affine constraints to construct a @math that preserves norms of all vectors in @math up to a distortion parameter @math . They then relax this problem to a convex program that can be solved using a tractable semidefinite program (SDP), with column generation for large data sets, and develop NuMax based on the Alternating Direction Method of Multipliers (ADMM). This framework deterministically produces a near-isometric linear embedding. Other algorithmic approaches for finding near-isometric linear embeddings are also described in @cite_10 @cite_2 @cite_11 .
@cite_2 @cite_11 @cite_10 @cite_17
2137825973 2083945855 1982831910 2063947013
We propose a novel framework for the deterministic construction of linear, near-isometric embeddings of a finite set of data points. Given a set of training points @math , we consider the secant set @math that consists of all pairwise difference vectors of @math , normalized to lie on the unit sphere. We formulate an affine rank minimization problem to construct a matrix @math that preserves the norms of all the vectors in @math up to a distortion parameter @math . While affine rank minimization is NP-hard, we show that this problem can be relaxed to a convex formulation that can be solved using a tractable semidefinite program (SDP). In order to enable scalability of our proposed SDP to very large-scale problems, we adopt a two-stage approach. First, in order to reduce compute time, we develop a novel algorithm based on the Alternating Direction Method of Multipliers (ADMM) that we call Nuclear norm minimization with Max-norm constraints (NuMax) to solve the SDP. Second, we develop a greedy, approximate version of NuMax based on the column generation method commonly used to solve large-scale linear programs. We demonstrate that our framework is useful for a number of signal processing applications via a range of experiments on large-scale synthetic and real datasets. 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. In this paper, we consider conic programming problems whose constraints consist of linear equalities, linear inequalities, a nonpolyhedral cone, and a polyhedral cone. A convenient way for solving this class of problems is to apply the directly extended alternating direction method of multipliers (ADMM) to its dual problem, which has been observed to perform well in numerical computations but may diverge in theory. Ideally, one should find a convergent variant which is at least as efficient as the directly extended ADMM in practice. We achieve this goal by designing a convergent semiproximal ADMM (called sPADMM3c for convenience) for convex programming problems having three separable blocks in the objective function with the third part being linear. At each iteration, the proposed sPADMM3c takes one special block coordinate descent (BCD) cycle with the order @math , instead of the usual @math Gauss--Seidel BCD cycle used in the nonconvergent directly extended 3-block ADMM, for updating the variable blocks. Our numerical experiments demonstrate that the convergent method is at least 20 faster than the directly extended ADMM with unit step-length for the vast majority of about 550 large-scale doubly nonnegative semidefinite programming problems with linear equality and or inequality constraints. This confirms that at least for conic convex programming, one can design a convergent and efficient ADMM with a special BCD cycle of updating the variable blocks. We consider the problem of estimating a deterministic finite alphabet vector @math from underdetermined measurements @math , where @math is a given (random) @math matrix. Two new convex optimization methods are introduced for the recovery of finite alphabet signals via @math -norm minimization. The first method is based on regularization. In the second approach, the problem is formulated as the recovery of sparse signals after a suitable sparse transform. The regularization-based method is less complex than the transform-based one. When the alphabet size @math equals 2 and @math grows proportionally, the conditions under which the signal will be recovered with high probability are the same for the two methods. When @math , the behavior of the transform-based method is established. Experimental results support this theoretical result and show that the transform method outperforms the regularization-based one.