The Experts below are selected from a list of 360 Experts worldwide ranked by ideXlab platform

Daniel Cremers - One of the best experts on this subject based on the ideXlab platform.

  • sublabel accurate Convex Relaxation of vectorial multilabel energies
    European Conference on Computer Vision, 2016
    Co-Authors: Emanuel Laude, Thomas Mollenhoff, Michael Moeller, Jan Lellmann, Daniel Cremers
    Abstract:

    Convex Relaxations of multilabel problems have been demonstrated to produce provably optimal or near-optimal solutions to a variety of computer vision problems. Yet, they are of limited practical use as they require a fine discretization of the label space, entailing a huge demand in memory and runtime. In this work, we propose the first sublabel accurate Convex Relaxation for vectorial multilabel problems. Our key idea is to approximate the dataterm in a piecewise Convex (rather than piecewise linear) manner. As a result we have a more faithful approximation of the original cost function that provides a meaningful interpretation for fractional solutions of the relaxed Convex problem.

  • sublabel accurate Convex Relaxation of vectorial multilabel energies
    arXiv: Computer Vision and Pattern Recognition, 2016
    Co-Authors: Emanuel Laude, Thomas Mollenhoff, Michael Moeller, Jan Lellmann, Daniel Cremers
    Abstract:

    Convex Relaxations of nonConvex multilabel problems have been demonstrated to produce superior (provably optimal or near-optimal) solutions to a variety of classical computer vision problems. Yet, they are of limited practical use as they require a fine discretization of the label space, entailing a huge demand in memory and runtime. In this work, we propose the first sublabel accurate Convex Relaxation for vectorial multilabel problems. The key idea is that we approximate the dataterm of the vectorial labeling problem in a piecewise Convex (rather than piecewise linear) manner. As a result we have a more faithful approximation of the original cost function that provides a meaningful interpretation for the fractional solutions of the relaxed Convex problem. In numerous experiments on large-displacement optical flow estimation and on color image denoising we demonstrate that the computed solutions have superior quality while requiring much lower memory and runtime.

  • Convex Relaxation of vectorial problems with coupled regularization
    Siam Journal on Imaging Sciences, 2014
    Co-Authors: Evgeny Strekalovskiy, Antonin Chambolle, Daniel Cremers
    Abstract:

    We propose Convex Relaxations for nonConvex energies on vector-valued functions which are tractable yet as tight as possible. In contrast to existing Relaxations, we can handle the combination of nonConvex data terms with coupled regularizers such as $l^2$-regularizers. The key idea is to consider a collection of hypersurfaces with a Relaxation that takes into account the entire functional rather than separately treating the data term and the regularizers. We provide a theoretical analysis, detail the implementations for different functionals, present run time and memory requirements, and experimentally demonstrate that the coupled $l^2$-regularizers give systematic improvements regarding denoising, inpainting, and optical flow estimation.

  • a Convex Relaxation approach to space time multi view 3d reconstruction
    International Conference on Computer Vision, 2013
    Co-Authors: Martin R Oswald, Daniel Cremers
    Abstract:

    We propose a Convex Relaxation approach to space-time 3D reconstruction from multiple videos. Generalizing the works Unger et al. [16], Kolev et al. [8] to the 4D setting, we cast the problem of reconstruction over time as a binary labeling problem in a 4D space. We propose a variational formulation which combines a photo consistency based data term with a spatio-temporal total variation regularization. In particular, we propose a novel data term that is both faster to compute and better suited for wide-baseline camera setups when photo consistency measures are unreliable or missing. The proposed functional can be globally minimized using Convex Relaxation techniques. Numerous experiments on a variety of public ally available data sets demonstrate that we can compute detailed and temporally consistent reconstructions. In particular, the temporal regularization allows to reduce jittering of voxels over time.

  • a Convex Relaxation approach for computing minimal partitions
    Computer Vision and Pattern Recognition, 2009
    Co-Authors: Thomas Pock, Daniel Cremers, Antonin Chambolle, Horst Bischof
    Abstract:

    In this work we propose a Convex Relaxation approach for computing minimal partitions. Our approach is based on rewriting the minimal partition problem (also known as Potts model) in terms of a primal dual Total Variation functional. We show that the Potts prior can be incorporated by means of Convex constraints on the dual variables. For minimization we propose an efficient primal dual projected gradient algorithm which also allows a fast implementation on parallel hardware. Although our approach does not guarantee to find global minimizers of the Potts model we can give a tight bound on the energy between the computed solution and the true minimizer. Furthermore we show that our Relaxation approach dominates recently proposed Relaxations. As a consequence, our approach allows to compute solutions closer to the true minimizer. For many practical problems we even find the global minimizer. We demonstrate the excellent performance of our approach on several multi-label image segmentation and stereo problems.

Joel A Tropp - One of the best experts on this subject based on the ideXlab platform.

  • solving ptychography with a Convex Relaxation
    New Journal of Physics, 2015
    Co-Authors: Roarke Horstmeyer, Joel A Tropp, Richard Y Chen, Brendan P W Ames, Changhuei Yang
    Abstract:

    Ptychography is a powerful computational imaging technique that transforms a collection of low-resolution images into a high-resolution sample reconstruction. Unfortunately, algorithms that currently solve this reconstruction problem lack stability, robustness, and theoretical guarantees. Recently, Convex optimization algorithms have improved the accuracy and reliability of several related reconstruction efforts. This paper proposes a Convex formulation of the ptychography problem. This formulation has no local minima, it can be solved using a wide range of algorithms, it can incorporate appropriate noise models, and it can include multiple a priori constraints. The paper considers a specific algorithm, based on low-rank factorization, whose runtime and memory usage are near-linear in the size of the output image. Experiments demonstrate that this approach offers a 25% lower background variance on average than alternating projections, the ptychographic reconstruction algorithm that is currently in widespread use.

  • Robust Computation of Linear Models by Convex Relaxation
    Foundations of Computational Mathematics, 2015
    Co-Authors: Gilad Lerman, Joel A Tropp, Michael B. Mccoy, Teng Zhang
    Abstract:

    Consider a data set of vector-valued observations that consists of noisy inliers, which are explained well by a low-dimensional subspace, along with some number of outliers. This work describes a Convex optimization problem, called reaper , that can reliably fit a low-dimensional model to this type of data. This approach parameterizes linear subspaces using orthogonal projectors and uses a Relaxation of the set of orthogonal projectors to reach the Convex formulation. The paper provides an efficient algorithm for solving the reaper problem, and it documents numerical experiments that confirm that reaper can dependably find linear structure in synthetic and natural data. In addition, when the inliers lie near a low-dimensional subspace, there is a rigorous theory that describes when reaper can approximate this subspace.

  • solving ptychography with a Convex Relaxation
    arXiv: Optics, 2014
    Co-Authors: Roarke Horstmeyer, Joel A Tropp, Richard Y Chen, Brendan P W Ames, Changhuei Yang
    Abstract:

    Ptychography is a powerful computational imaging technique that transforms a collection of low-resolution images into a high-resolution sample reconstruction. Unfortunately, algorithms that are currently used to solve this reconstruction problem lack stability, robustness, and theoretical guarantees. Recently, Convex optimization algorithms have improved the accuracy and reliability of several related reconstruction efforts. This paper proposes a Convex formulation of the ptychography problem. This formulation has no local minima, it can be solved using a wide range of algorithms, it can incorporate appropriate noise models, and it can include multiple a priori constraints. The paper considers a specific algorithm, based on low-rank factorization, whose runtime and memory usage are near-linear in the size of the output image. Experiments demonstrate that this approach offers a 25% lower background variance on average than alternating projections, the current standard algorithm for ptychographic reconstruction.

  • algorithms for simultaneous sparse approximation part ii Convex Relaxation
    Signal Processing, 2006
    Co-Authors: Joel A Tropp
    Abstract:

    A simultaneous sparse approximation problem requests a good approximation of several input signals at once using different linear combinations of the same elementary signals. At the same time, the problem balances the error in approximation against the total number of elementary signals that participate. These elementary signals typically model coherent structures in the input signals, and they are chosen from a large, linearly dependent collection.The first part of this paper presents theoretical and numerical results for a greedy pursuit algorithm, called simultaneous orthogonal matching pursuit.The second part of the paper develops another algorithmic approach called Convex Relaxation. This method replaces the combinatorial simultaneous sparse approximation problem with a closely related Convex program that can be solved efficiently with standard mathematical programming software. The paper develops conditions under which Convex Relaxation computes good solutions to simultaneous sparse approximation problems.

  • just relax Convex programming methods for identifying sparse signals in noise
    IEEE Transactions on Information Theory, 2006
    Co-Authors: Joel A Tropp
    Abstract:

    This paper studies a difficult and fundamental problem that arises throughout electrical engineering, applied mathematics, and statistics. Suppose that one forms a short linear combination of elementary signals drawn from a large, fixed collection. Given an observation of the linear combination that has been contaminated with additive noise, the goal is to identify which elementary signals participated and to approximate their coefficients. Although many algorithms have been proposed, there is little theory which guarantees that these algorithms can accurately and efficiently solve the problem. This paper studies a method called Convex Relaxation, which attempts to recover the ideal sparse signal by solving a Convex program. This approach is powerful because the optimization can be completed in polynomial time with standard scientific software. The paper provides general conditions which ensure that Convex Relaxation succeeds. As evidence of the broad impact of these results, the paper describes how Convex Relaxation can be used for several concrete signal recovery problems. It also describes applications to channel coding, linear regression, and numerical analysis

Tong Zhang - One of the best experts on this subject based on the ideXlab platform.

  • Multi-stage Convex Relaxation for feature selection
    Bernoulli, 2013
    Co-Authors: Tong Zhang
    Abstract:

    A number of recent work studied the effectiveness of feature selection using Lasso. It is known that under the restricted isometry properties (RIP), Lasso does not generally lead to the exact recovery of the set of nonzero coefficients, due to the looseness of Convex Relaxation. This paper considers the feature selection property of nonConvex regularization, where the solution is given by a multi-stage Convex Relaxation scheme. The nonConvex regularizer requires two tuning parameters (compared to one tuning parameter for Lasso). Although the method is more complex than Lasso, we show that under appropriate conditions including the dependence of a tuning parameter on the support set size, the local solution obtained by this procedure recovers the set of nonzero coefficients without suffering from the bias of Lasso Relaxation, which complements parameter estimation results of this procedure in (J. Mach. Learn. Res.11 (2011) 1087–1107).

  • Multi-stage Convex Relaxation for Feature Selection
    arXiv: Machine Learning, 2011
    Co-Authors: Tong Zhang
    Abstract:

    A number of recent work studied the effectiveness of feature selection using Lasso. It is known that under the restricted isometry properties (RIP), Lasso does not generally lead to the exact recovery of the set of nonzero coefficients, due to the looseness of Convex Relaxation. This paper considers the feature selection property of nonConvex regularization, where the solution is given by a multi-stage Convex Relaxation scheme. Under appropriate conditions, we show that the local solution obtained by this procedure recovers the set of nonzero coefficients without suffering from the bias of Lasso Relaxation, which complements parameter estimation results of this procedure.

  • analysis of multi stage Convex Relaxation for sparse regularization
    Journal of Machine Learning Research, 2010
    Co-Authors: Tong Zhang
    Abstract:

    We consider learning formulations with non-Convex objective functions that often occur in practical applications. There are two approaches to this problem: Heuristic methods such as gradient descent that only find a local minimum. A drawback of this approach is the lack of theoretical guarantee showing that the local minimum gives a good solution. Convex Relaxation such as L1-regularization that solves the problem under some conditions. However it often leads to a sub-optimal solution in reality. This paper tries to remedy the above gap between theory and practice. In particular, we present a multi-stage Convex Relaxation scheme for solving problems with non-Convex objective functions. For learning formulations with sparse regularization, we analyze the behavior of a specific multi-stage Relaxation scheme. Under appropriate conditions, we show that the local solution obtained by this procedure is superior to the global solution of the standard L1 Convex Relaxation for learning sparse targets.

  • multi stage Convex Relaxation for learning with sparse regularization
    Neural Information Processing Systems, 2008
    Co-Authors: Tong Zhang
    Abstract:

    We study learning formulations with non-Convex regularizaton that are natural for sparse linear models. There are two approaches to this problem: • Heuristic methods such as gradient descent that only find a local minimum. A drawback of this approach is the lack of theoretical guarantee showing that the local minimum gives a good solution. • Convex Relaxation such as L1-regularization that solves the problem under some conditions. However it often leads to sub-optimal sparsity in reality. This paper tries to remedy the above gap between theory and practice. In particular, we investigate a multi-stage Convex Relaxation scheme for solving problems with non-Convex regularization. Theoretically, we analyze the behavior of a resulting two-stage Relaxation scheme for the capped-L1 regularization. Our performance bound shows that the procedure is superior to the standard L1 Convex Relaxation for learning sparse targets. Experiments confirm the effectiveness of this method on some simulation and real data.

Pengchuan Zhang - One of the best experts on this subject based on the ideXlab platform.

  • a Convex Relaxation barrier to tight robustness verification of neural networks
    Neural Information Processing Systems, 2019
    Co-Authors: Hadi Salman, Greg Yang, Huan Zhang, Chojui Hsieh, Pengchuan Zhang
    Abstract:

    Verification of neural networks enables us to gauge their robustness against adversarial attacks. Verification algorithms fall into two categories: exact verifiers that run in exponential time and relaxed verifiers that are efficient but incomplete. In this paper, we unify all existing LP-relaxed verifiers, to the best of our knowledge, under a general Convex Relaxation framework. This framework works for neural networks with diverse architectures and nonlinearities and covers both primal and dual views of neural network verification. Next, we perform large-scale experiments, amounting to more than 22 CPU-years, to obtain exact solution to the Convex-relaxed problem that is optimal within our framework for ReLU networks. We find the exact solution does not significantly improve upon the gap between PGD and existing relaxed verifiers for various networks trained normally or robustly on MNIST and CIFAR datasets. Our results suggest there is an inherent barrier to tight verification for the large class of methods captured by our framework. We discuss possible causes of this barrier and potential future directions for bypassing it.

  • a Convex Relaxation barrier to tight robustness verification of neural networks
    arXiv: Learning, 2019
    Co-Authors: Hadi Salman, Greg Yang, Huan Zhang, Chojui Hsieh, Pengchuan Zhang
    Abstract:

    Verification of neural networks enables us to gauge their robustness against adversarial attacks. Verification algorithms fall into two categories: exact verifiers that run in exponential time and relaxed verifiers that are efficient but incomplete. In this paper, we unify all existing LP-relaxed verifiers, to the best of our knowledge, under a general Convex Relaxation framework. This framework works for neural networks with diverse architectures and nonlinearities and covers both primal and dual views of robustness verification. We further prove strong duality between the primal and dual problems under very mild conditions. Next, we perform large-scale experiments, amounting to more than 22 CPU-years, to obtain exact solution to the Convex-relaxed problem that is optimal within our framework for ReLU networks. We find the exact solution does not significantly improve upon the gap between PGD and existing relaxed verifiers for various networks trained normally or robustly on MNIST and CIFAR datasets. Our results suggest there is an inherent barrier to tight verification for the large class of methods captured by our framework. We discuss possible causes of this barrier and potential future directions for bypassing it. Our code and trained models are available at this http URL .

Joao Gomes - One of the best experts on this subject based on the ideXlab platform.

  • simple and fast Convex Relaxation method for cooperative localization in sensor networks using range measurements
    IEEE Transactions on Signal Processing, 2015
    Co-Authors: Claudia Soares, Joao Xavier, Joao Gomes
    Abstract:

    We address the sensor network localization problem given noisy range measurements between pairs of nodes. We approach the nonConvex maximum-likelihood formulation via a known simple Convex Relaxation. We exploit its favorable optimization properties to the full to obtain an approach that is completely distributed, has a simple implementation at each node, and capitalizes on an optimal gradient method to attain fast convergence. We offer a parallel but also an asynchronous flavor, both with theoretical convergence guarantees and iteration complexity analysis. Experimental results establish leading performance. Our algorithms top the accuracy of a comparable state-of-the-art method by one order of magnitude, using one order of magnitude fewer communications.

  • an angular approach for range based approximate maximum likelihood source localization through Convex Relaxation
    IEEE Transactions on Wireless Communications, 2014
    Co-Authors: Pinar Oguzekim, Joao Xavier, Joao Gomes, Marko Stosic, Paulo Oliveira
    Abstract:

    This work considers the problem of locating a single source from noisy range measurements to a set of nodes in a wireless sensor network. We propose two new techniques that we designate as Source Localization with Nuclear Norm (SLNN) and Source Localization with l 1 -norm (SL-l 1 ), which extend to arbitrary real dimensions our prior work on 2D source localization formulated in the complex plane. Our approach is based on formulating a Maximum-Likelihood (ML) estimation problem, and then using Convex Relaxation techniques to obtain a semidefinite program (SDP) that can be globally and efficiently solved. SLNN directly approximates the Gaussian ML solution, and the Relaxation is shown to be tighter than in other methods in the same class. We present an analysis of the Convexity properties of the constraint set for the 2D complex version of SLNN (SLCP) to justify the observed tightness of the Relaxation. We propose the SL-l 1 algorithm to address the Laplacian noise case, which models the presence of outliers in range measurements. We overcome the non-differentiability of the Laplacian likelihood function by rewriting the ML problem as an exact weighted version of the Gaussian case. In terms of accuracy of localization, the proposed algorithms globally outperform state-of-the-art optimization-based methods in different noise scenarios, while exhibiting moderate computational complexity.