Given an undirected graph and a size parameter k, the Densest k-Subgraph (DkS) problem extracts the subgraph on k vertices with the largest number of induced edges. While DkS is NP--hard and difficult to approximate, penalty-based continuous relaxations of the problem have recently enjoyed practical success for real-world instances of DkS. In this work, we propose a scalable and exact continuous penalization approach for DkS using the error bound principle, which enables the design of suitable penalty functions. Notably, we develop new theoretical guarantees ensuring that both the global and local optima of the penalized problem match those of the original problem. The proposed penalized reformulation enables the use of first-order continuous optimization methods. In particular, we develop a non-convex proximal gradient algorithm, where the non-convex proximal operator can be computed in closed form, resulting in low per-iteration complexity. We also provide convergence analysis of the algorithm. Experiments on large-scale instances of the DkS problem and one of its variants, the Densest (k1, k2) Bipartite Subgraph (Dk1k2BS) problem, demonstrate that our method achieves a favorable balance between computation cost and solution quality.

Multilayer matrix factorization (MMF) has recently emerged as a generalized model of, and potentially a more expressive approach than, the classic matrix factorization. This paper considers MMF under a probabilistic formulation, and our focus is on inference methods under variational inference. The challenge in this context lies in determining a variational process that leads to a computationally efficient and accurate approximation of the maximum likelihood inference. One well-known example is the variational autoencoder (VAE), which uses neural networks for the variational process. In this work, we take insight from variational diffusion models in the context of generative models to develop variational inference for MMF. We propose a dimension-reducing diffusion process that results in a new way to interact with the layered structures of the MMF model. Experimental results demonstrate that the proposed diffusion variational inference method leads to improved performance scores compared to several existing methods, including the VAE.

Cardinality-constrained binary quadratic optimization appears in various applications such as finding a densest size-constrained subgraph from a graph. It is a challenging combinatorial problem, and in this paper we tackle the problem by a continuous optimization approach. Our method, called the extreme point pursuit, works by relaxing the cardinality-constrained binary set to its corresponding convex hull, and then by adding an appropriate penalty function to encourage the solution to be an extreme point of the convex hull. The resulting extreme-point pursuit formulation is non-convex. As an intuitive strategy to try to avoid poor local minima, we adopt a homotopy optimization method wherein we start with an easy convex problem and gradually change the landscape of the problem to approach the extreme-point pursuit formulation. Experiments based on real-world large-scale graph data are performed to demonstrate the performance and efficiency of our method.

In this paper we examine the application of variational inference (VI) to MIMO detection. Our study is motivated by the recent interest in applying machine learning concepts to signal processing. VI is an approach for providing friendly approximations of certain intractable posterior probabilities in statistics, and it has been popularly used in machine learning. In MIMO detection we also have a similar problem; specifically, we want to evaluate the posterior symbol probabilities for detection, but they are computationally too expensive to evaluate when the problem size and/or the constellation size are large. By approximating the discrete symbol prior by a continuous Gaussian mixture model, we show how the notion of VI can be used to derive an iterative MIMO detector. Interestingly, the detector resembles the MMSE detector in structure. The performance of the proposed detector is demonstrated by simulations.

This article proposes a novel synthetic aperture radar visual-inertial odometry (SAR-VIO) consisting of an SAR and an inertial measurement unit (IMU), which aims to enable the observation platform to complete successfully a continuous observation mission in the context of low-cost demand and lack of enough navigation information. First, we establish the observation models of the SAR in a continuous observation process based on the SAR frequency-domain imaging algorithm and the SAR time-domain imaging algorithm, respectively. With the preintegrated IMU data, we then propose a method for estimating the geographic locations of the matched targets in the SAR images and verify the condition and correctness of the method. The optimization of the track and the locations of the targets is achieved by bundle adjustment according to the minimum reprojection error criterion, and a sparse point-cloud map can be obtained. Finally, these methods and models are organized into a complete SAR-VIO framework, and the feasibility of the framework is verified through experiments.

The theoretical modeling and analysis of SAR location error play an important role in SAR system design and error source budget. Existing SAR geolocation error models are mainly implicit, which are not easy to do analysis, especially in the curved-path case. In this paper, a theoretical explicit model of the relationship between image geolocation error and the path measurement error is established for curved-path SAR, based on BP imaging algorithm. Simulations are given which verify the correctness of the model. The explicit model and the analysis results provide an effective reference for understanding and budgeting the system-level geometric location error for curved-path SAR, such as GeoSAR.

Real-time target tracking is an important service provided by embedded camera networks. The first step in target tracking is to extract the moving targets from the video frames, which can be realised by using background subtraction. For a background subtraction method to be useful in embedded camera networks, it must be both accurate and computationally efficient because of the resource constraints on embedded platforms. This makes many traditional background subtraction algorithms unsuitable for embedded platforms because they use complex statistical models to handle subtle illumination changes. These models make them accurate but the computational requirement of these complex models is often too high for embedded platforms. In this paper, we propose a new background subtraction method which is both accurate and computationally efficient. We propose a baseline version which uses luminance only and then extend it to use colour information. The key idea is to use random projection matrics to reduce the dimensionality of the data while retaining most of the information. By using multiple datasets, we show that the accuracy of our proposed background subtraction method is comparable to that of the traditional background subtraction methods. Moreover, to show the computational efficiency of our methods is not platform specific, we implement it on various platforms. The real implementation shows that our proposed method is consistently better and is up to six times faster, and consume significantly less resources than the conventional approaches. Finally, we demonstrated the feasibility of the proposed method by the implementation and evaluation of an end-to-end real-time embedded camera network target tracking application.

The selection of optimal camera configurations (camera locations, orientations, etc.) for multi-camera networks remains an unsolved problem. Previous approaches largely focus on proposing various objective functions to achieve different tasks. Most of them, however, do not generalize well to large scale networks. To tackle this, we propose a statistical framework of the problem as well as propose a trans-dimensional simulated annealing algorithm to effectively deal with it. We compare our approach with a state-of-the-art method based on binary integer programming (BIP) and show that our approach offers similar performance on small scale problems. However, we also demonstrate the capability of our approach in dealing with large scale problems and show that our approach produces better results than two alternative heuristics designed to deal with the scalability issue of BIP. Last, we show the versatility of our approach using a number of specific scenarios.

Background subtraction is often the first step in many computer vision applications such as object localisation and tracking. It aims to segment out moving parts of a scene that represent object of interests. In the field of computer vision, researchers have dedicated their efforts to improve the robustness and accuracy of such segmentations but most of their methods are computationally intensive, making them non-viable options for our targeted embedded camera platform whose energy and processing power is significantly more constrained. To address this problem as well as maintain an acceptable level of performance, we introduce Compressive Sensing (CS) to the widely used Mixture of Gaussian to create a new background subtraction method. The results show that our method not only can decrease the computation significantly (a factor of 7 in a DSP setting) but remains comparably accurate.

Background subtraction is often the first step of many computer vision applications. For a background subtraction method to be useful in embedded camera networks, it must be both accurate and computationally efficient because of the resource constraints on embedded platforms. This makes many traditional background subtraction algorithms unsuitable for embedded platforms because they use complex statistical models to handle subtle illumination changes. These models make them accurate but the computational requirement of these complex models is often too high for embedded platforms. In this paper, we propose a new background subtraction method which is both accurate and computational efficient. The key idea is to use compressive sensing to reduce the dimensionality of the data while retaining most of the information. By using multiple datasets, we show that the accuracy of our proposed background subtraction method is comparable to that of the traditional background subtraction methods. Moreover, real implementation on an embedded camera platform shows that our proposed method is at least 5 times faster, and consumes significantly less energy and memory resources than the conventional approaches. Finally, we demonstrated the feasibility of the proposed method by the implementation and evaluation of an end-to-end real-time embedded camera network target tracking application.

We describe our current work towards a framework that establishes a hierarchy of devices (sensors and actuators) within a wireless multimedia node and uses frequent sampling of cheaper devices to trigger the activation of more energy-hungry devices. Within this framework, we consider the suitability of servos for Wireless Multimedia Sensor Networks (WMSNs) by examining their functional characteristics and energy consumption [2].