We propose a novel randomized algorithm for constructing binary neural networks with tunable accuracy. This approach is motivated by hyperdimensional computing (HDC), which is a brain-inspired paradigm that leverages high-dimensional vector representations, offering efficient hardware implementation and robustness to model corruptions. Unlike traditional low-precision methods that use quantization, we consider binary embeddings of data as points in the hypercube equipped with the Hamming distance. We propose a novel family of floating-point neural networks, G-Nets, which are general enough to mimic standard network layers. Each floating-point G-Net has a randomized binary embedding, an embedded hyperdimensional (EHD) G-Net, that retains the accuracy of its floating-point counterparts, with theoretical guarantees, due to the concentration of measure. Empirically, our binary models match convolutional neural network accuracies and outperform prior HDC models by large margins, for example, we achieve almost 30\% higher accuracy on CIFAR-10 compared to prior HDC models. G-Nets are a theoretically justified bridge between neural networks and randomized binary neural networks, opening a new direction for constructing robust binary/quantized deep learning models. Our implementation is available at \url{https://github.com/GNet2025/GNet}.

This paper studies the geometry of binary hyperdimensional computing (HDC), a computational scheme in which data are encoded using high-dimensional binary vectors. We establish a result about the similarity structure induced by the HDC binding operator and show that the Laplace kernel naturally arises in this setting, motivating our new encoding method Laplace-HDC, which improves upon previous methods. We describe how our results indicate limitations of binary HDC in encoding spatial information from images and discuss potential solutions, including using Haar convolutional features and the definition of a translation-equivariant HDC encoding. Several numerical experiments highlighting the improved accuracy of Laplace-HDC in contrast to alternative methods are presented. We also numerically study other aspects of the proposed framework, such as robustness and the underlying translation-equivariant encoding.

We consider a discrete-time model of continuous-time distributed optimization over dynamic directed-graphs (digraphs) with applications to distributed learning. Our optimization algorithm works over general strongly connected dynamic networks under switching topologies, e.g., in mobile multi-agent systems and volatile networks due to link failures. Compared to many existing lines of work, there is no need for bi-stochastic weight designs on the links. The existing literature mostly needs the link weights to be stochastic using specific weight-design algorithms needed both at the initialization and at all times when the topology of the network changes. This paper eliminates the need for such algorithms and paves the way for distributed optimization over time-varying digraphs. We derive the bound on the gradient-tracking step-size and discrete time-step for convergence and prove dynamic stability using arguments from consensus algorithms, matrix perturbation theory, and Lyapunov theory. This work, particularly, is an improvement over existing stochastic-weight undirected networks in case of link removal or packet drops. This is because the existing literature may need to rerun time-consuming and computationally complex algorithms for stochastic design, while the proposed strategy works as long as the underlying network is weight-symmetric and balanced. The proposed optimization framework finds applications to distributed classification and learning.Note to Practitioners—Inspired by recent advances in cloud-computing and distributed and parallel processing along with embedded low-cost CPUs and wireless communications, this paper considers distributed algorithms for optimization and machine learning over wireless-connected autonomous multi-agent systems (MASs). In contrast to the classical centralized learning methods, which are prone to single-point-of-failure and centralized processing, in cooperative optimization the learning is distributed among a group of data-processing agents (e.g. robots) with communication units. This article provides an efficient algorithm to enable MASs to collaboratively optimize a cost function, e.g., for binary classification and distributed support vector machine (D-SVM). Sampled data systems related to MASs and robotic networks, due to digital communications and discretized control models, use discrete-time algorithms that need to account for intermittent communications and dynamic networking. This requires discretized algorithms overdynamicdigraphs, practical in the presence of packet drops (or lost communication channels). Most existing distributed algorithms either are susceptible to change in the communication network or impose computationally inefficient stochastic design. These algorithms need to be rerun, for example, whenever the mobile robotic network changes due to limited communication range. This makes most existing algorithms infeasible in real-time applications. Our proposed method outperforms similar algorithms over dynamic robotic networks and in the presence of link removal (packet drops). We show this efficiency of our distributed optimization method by simulation.

Given the abundance of images related to operations that are being captured and stored, it behooves firms to innovate systems using image processing to improve operational performance that refers to any activity that can save labor cost. In this paper, we use deep learning techniques, combined with classic image/signal processing methods, to propose a pipeline to solve certain types of object counting and layer characterization problems in firm operations. Using data obtained by us through a collaborative effort with real manufacturers, we demonstrate that the proposed pipeline method is able to achieve higher than 93% accuracy in layer and log counting. Theoretically, our study conceives, constructs, and evaluates proof of concept of a novel pipeline method in characterizing and quantifying the number of defined items with images, which overcomes the limitations of methods based only on deep learning or signal processing. Practically, our proposed method can help firms significantly reduce labor costs and/or improve quality and inventory control by recording the number of products in real time, more accurately and with minimal up-front technological investment. The codes and data are made publicly available online through the INFORMS Journal on Computing GitHub site. History: Accepted by Ram Ramesh, Area Editor for Data Science and Machine Learning. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0260 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0260 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Distributed allocation finds applications in many scenarios including CPU scheduling, distributed energy resource management, and networked coverage control. In this paper, we propose a fast convergent optimization algorithm with a tunable rate using the signum function. The convergence rate of the proposed algorithm can be managed by changing two parameters. We prove convergence over uniformly-connected multi-agent networks. Therefore, the solution converges even if the network loses connectivity at some finite time intervals. The proposed algorithm is all-time feasible, implying that at any termination time of the algorithm, the resource-demand feasibility holds. This is in contrast to asymptotic feasibility in many dual formulation solutions (e.g., ADMM) that meet resource-demand feasibility over time and asymptotically.

Motivated by recent development in networking and parallel data-processing, we consider a distributed and localized finite-sum (or fixed-sum) allocation technique to solve resource-constrained convex optimization problems over multi-agent networks (MANs). Such networks include (smart) agents representing an intelligent entity capable of communication, processing, and decision-making. In particular, we consider problems subject to practical nonlinear constraints on the dynamics of the agents in terms of their communications and actuation capabilities (referred to as the node dynamics), e.g., networks of mobile robots subject to actuator saturation and quantized communication. The considered distributed sum-preserving optimization solution further enables adding purposeful nonlinear constraints, for example, sign-based nonlinearities, to reach convergence in predefined-time or robust to impulsive noise and disturbances in faulty environments. Moreover, convergence can be achieved under minimal network connectivity requirements among the agents; thus, the solution is applicable over dynamic networks where the channels come and go due to the agent’s mobility and limited range. This paper discusses how various nonlinearity constraints on the optimization problem (e.g., collaborative allocation of resources) can be addressed for different applications via a distributed setup (over a network).

In real world settings, numerous constraints are present which are hard to specify mathematically. However, for the real world deployment of reinforcement learning (RL), it is critical that RL agents are aware of these constraints, so that they can act safely. In this work, we consider the problem of learning constraints from demonstrations of a constraint-abiding agent’s behavior. We experimentally validate our approach and show that our framework can successfully learn the most likely constraints that the agent respects. We further show that these learned constraints are \textit{transferable} to new agents that may have different morphologies and/or reward functions. Previous works in this regard have either mainly been restricted to tabular (discrete) settings, specific types of constraints or assume the environment’s transition dynamics. In contrast, our framework is able to learn arbitrary \textit{Markovian} constraints in high-dimensions in a completely model-free setting. The code is available at: \url{https://github.com/shehryar-malik/icrl}.

We consider the task of recovering two real or complex $m$-vectors from phaseless Fourier measurements of their circular convolution. Our method is a novel convex relaxation that is based on a lifted matrix recovery formulation that allows a non-trivial convex relaxation of the bilinear measurements from convolution. We prove that if the two signals belong to known random subspaces of dimensions $k$ and $n$, then they can be recovered up to the inherent scaling ambiguity with $m \gg (k+n) \log^2 m$ phaseless measurements. Our method provides the first theoretical recovery guarantee for this problem by a computationally efficient algorithm and does not require a solution estimate to be computed for initialization. Our proof is based on Rademacher complexity estimates. Additionally, we provide an alternating direction method of multipliers (ADMM) implementation and provide numerical experiments that verify the theory.

We consider the bilinear inverse problem of recovering two vectors, x in R^L and w in R^L, from their entrywise product. We consider the case where x and w have known signs and are sparse with respect to known dictionaries of size K and N, respectively. Here, K and N may be larger than, smaller than, or equal to L. We introduce L1-BranchHull, which is a convex program posed in the natural parameter space and does not require an approximate solution or initialization in order to be stated or solved. We study the case where x and w are S1- and S2-sparse with respect to a random dictionary, with the sparse vectors satisfying an effective sparsity condition, and present a recovery guarantee that depends on the number of measurements as L > Omega(S1+S2)(log(K+N))^2. Numerical experiments verify that the scaling constant in the theorem is not too large. One application of this problem is the sweep distortion removal task in dielectric imaging, where one of the signals is a nonnegative reflectivity, and the other signal lives in a known subspace, for example that given by dominant wavelet coefficients. We also introduce a variants of L1-BranchHull for the purposes of tolerating noise and outliers, and for the purpose of recovering piecewise constant signals. We provide an ADMM implementation of these variants and show they can extract piecewise constant behavior from real images.

We consider the task of recovering two real or complex $m$-vectors from phaseless Fourier measurements of their circular convolution. Our method is a novel convex relaxation that is based on a lifted matrix recovery formulation that allows a nontrivial convex relaxation of the bilinear measurements from convolution. We prove that if the two signals belong to known random subspaces of dimensions $k$ and $n$, then they can be recovered up to the inherent scaling ambiguity with $m >> (k+n) \log^2 m$ phaseless measurements. Our method provides the first theoretical recovery guarantee for this problem by a computationally efficient algorithm and does not require a solution estimate to be computed for initialization. Our proof is based Rademacher complexity estimates. Additionally, we provide an ADMM implementation of the method and provide numerical experiments that verify the theory.

We present a general method for extracting a region from an image (or 3D object) that can be expressed, or approximated, by taking unions and set differences from a collection of template shapes in a dictionary. We build on recent work that shows how this geometric problem can be recast in the language of linear algebra, with set operations on shapes translated into linear combinations of vectors, and solved using convex programming. This paper presents a set of sufficient conditions for which this convex program returns the "correct" shape. These conditions are robust in that they can account for the shapes that have indistinct boundaries, or model mismatch between the shapes in the dictionary and the target region in the image. We also present two different methods for solving the convex extraction program. The first method simply recasts the problem as a linear program, while the second uses the alternating direction method of multipliers with a series of easily computed proximal operators. We present a number of numerical experiments that use the framework to perform image segmentation, optical character recognition, and find multi-resolution geometrical descriptions of 3D objects.

We introduce and analyze a new technique for model reduction for deep neural networks. While large networks are theoretically capable of learning arbitrarily complex models, overfitting and model redundancy negatively affects the prediction accuracy and model variance. Our Net-Trim algorithm prunes (sparsifies) a trained network layer-wise, removing connections at each layer by solving a convex optimization program. This program seeks a sparse set of weights at each layer that keeps the layer inputs and outputs consistent with the originally trained model. The algorithms and associated analysis are applicable to neural networks operating with the rectified linear unit (ReLU) as the nonlinear activation. We present both parallel and cascade versions of the algorithm. While the latter can achieve slightly simpler models with the same generalization performance, the former can be computed in a distributed manner. In both cases, Net-Trim significantly reduces the number of connections in the network, while also providing enough regularization to slightly reduce the generalization error. We also provide a mathematical analysis of the consistency between the initial network and the retrained model. To analyze the model sample complexity, we derive the general sufficient conditions for the recovery of a sparse transform matrix. For a single layer taking independent Gaussian random vectors of length $N$ as inputs, we show that if the network response can be described using a maximum number of $s$ non-zero weights per node, these weights can be learned from $\mathcal{O}(s\log N)$ samples.

We propose a new shape-based modeling technique for applications in imaging problems. Given a collection of shape priors (a shape dictionary), we define our problem as choosing the right dictionary elements and geometrically composing them through basic set operations to characterize desired regions in an image. This is a combinatorial problem solving which requires an exhaustive search among a large number of possibilities. We propose a convex relaxation to the problem to make it computationally tractable. We take some major steps towards the analysis of the proposed convex program and characterizing its minimizers. Applications vary from shape-based characterization, object tracking, optical character recognition, and shape recovery in occlusion to other disciplines such as the geometric packing problem.

In this work, we present POUTINE, a novel estimator of the auto-correlation function (or more generally, the cross-correlation function) of ergodic stationary signals, an important task in a variety of applications. This estimator sparsely and non-adaptively samples the process via Bernoulli selection, generalizing the classical estimator in a natural way, and offering significant sampling reductions while sacrificing a modest degree of accuracy. Both the mean and variance of our estimator are explicitly analyzed, and in particular, we show that POUTINE gives an unbiased estimate of the classical estimator, which in turn gives an unbiased estimate of the underlying second-order statistics of interest. Furthermore, we show that POUTINE is a consistent estimator with variance approaching zero asymptotically. We demonstrate favorable performance of this approach for a simple stochastic process.

This paper introduces a new shape-based image reconstruction technique applicable to a large class of imaging problems formulated in a variational sense. Given a collection of shape priors (a shape dictionary), we define our problem as choosing the right elements and geometrically composing them through basic set operations to characterize desired regions in the image. This combinatorial problem can be relaxed and then solved using classical descent methods. The main component of this relaxation is forming certain compactly supported functions which we call “knolls” and reformulating the shape representation as a basis expansion in terms of such functions. To select suitable elements of the dictionary, our problem ultimately reduces to solving a nonlinear program with sparsity constraints. We provide a new sparse nonlinear reconstruction technique to approach this problem. The performance of the proposed technique is demonstrated with some standard imaging problems including image segmentation, X-ray tomography, and diffusive tomography.

Remediation of sites polluted by hazardous chemicals such as dense non-aqueous phase liquids (DNAPLs) represents an important environmental problem due to the large scale threat these releases pose to water supplies throughout the world. Successful cleanup and restoration relies on methods to characterize the source zone structure prior to remediation and subsequently to monitor the corresponding dissolved chemical levels. This paper develops and implements a new model-based approach to DNAPL source zone characterization based on the joint inversion of hydrological and geophysical data. To model the interaction of groundwater with the contaminant source zone, a fully three dimensional (3D) flow and transport model is used to provide the downstream contaminant concentrations associated to the source zone saturation distribution. As the geophysical modality we utilize electrical resistance tomography (ERT) where electric potential measurements related to the electrical properties of the medium are obtained cross gradient to the water flow direction. The inversion technique is based on the parametric level set method (PaLS) which provides for the recovery of the geometric profiles of the low and high saturation regions (corresponding to the ganglia and the pooling regions) and low order characterizations of the spatial variability within each region. The performance of our proposed algorithm is examined and discussed through the reconstruction of some challenging source zone architectures.

Adjoint field methods are both elegant and efficient for calculating sensitivity information required across a wide range of physics-based inverse problems. In this letter, we provide a unified approach to the derivation of such methods for problems whose physics are provided by Poisson's equation. Unlike existing approaches in the literature, we consider in detail and explicitly the role of general boundary conditions in the derivation of the associated adjoint-field-based sensitivities. We highlight the relationship between the adjoint field computations required for both gradient decent and Gauss-Newton approaches to image formation. Our derivation is based on standard results from vector calculus coupled with transparent manipulation of the underlying partial different equations, thereby making the concepts employed in this letter easily adaptable to other systems of interest.

We present a novel approach for the inverse problem in electrical impedance tomography based on regularized quadratic regression. Our contribution introduces a new formulation for the forward model in the form of a nonlinear integral transform, which maps changes in the electrical properties of a domain to their respective variations in boundary data. Using perturbation theory the transform is approximated to yield a high-order misfit function which is then used to derive a regularized inverse problem. In particular, we consider the nonlinear problem to second-order accuracy; hence our approximation method improves upon the local linearization of the forward mapping. The inverse problem is approached using Newton's iterative algorithm, and results from simulated experiments are presented. With a moderate increase in computational complexity, the method yields superior results compared to those of regularized linear regression and can be implemented to address the nonlinear inverse problem.

In this paper, a parametric level set method for reconstruction of obstacles in general inverse problems is considered. General evolution equations for the reconstruction of unknown obstacles are derived in terms of the underlying level set parameters. We show that using the appropriate form of parameterizing the level set function results in a significantly lower dimensional problem, which bypasses many difficulties with traditional level set methods, such as regularization, reinitialization, and use of signed distance function. Moreover, we show that from a computational point of view, low order representation of the problem paves the way for easier use of Newton and quasi-Newton methods. Specifically for the purposes of this paper, we parameterize the level set function in terms of adaptive compactly supported radial basis functions, which, used in the proposed manner, provide flexibility in presenting a larger class of shapes with fewer terms. Also they provide a “narrow-banding” advantage which can further reduce the number of active unknowns at each step of the evolution. The performance of the proposed approach is examined in three examples of inverse problems, i.e., electrical resistance tomography, X-ray computed tomography, and diffuse optical tomography.

This paper presents a new synthesis algorithm to produce flat-top main beams with arbitrary footprint for array elements placed in an arbitrary planar geometry. The general framework of the paper would encompass the patterns produced by circular aperture distribution. It is shown that for patterns generated by circular apertures some efficient simplifying facts based on properties of Bessel functions can be applied. The method shows a high performance in generating optimally flat-top patterns with detailed geometry footprints.