Search

In this paper, we study Stochastic Composite Optimization (SCO) for sparse learning that aims to learn a sparse solution from a composite function. Most of the recent SCO algorithms have already reached the optimal expected convergence rate \mathcal O(1/\lambda T) , but they often fail to deliver sparse solutions at the end either due to the limited sparsity regularization during stochastic optimization (SO) or due to the limitation in online-to-batch conversion. Even when the objective function is strongly convex, their high probability bounds can only attain \mathcal O(\sqrt\log (1/\delta)/T) with $\delta$ is the failure probability, which is much worse than the expected convergence rate. To address these limitations, we propose a simple yet effective two-phase Stochastic Composite Optimization scheme by adding a novel powerful sparse online-to-batch conversion to the general Stochastic Optimization algorithms. We further develop three concrete algorithms, OptimalSL, LastSL and AverageSL, directly under our scheme to prove the effectiveness of the proposed scheme. Both the theoretical analysis and the experiment results show that our methods can really outperform the existing methods at the ability of sparse learning and at the meantime we can improve the high probability bound to approximately \mathcal {O}(\log (\log (T)/\delta)/\lambda T) . [ABSTRACT FROM AUTHOR]

Hashing based methods have attracted considerable attention for efficient cross-modal retrieval on large-scale multimedia data. The core problem of cross-modal hashing is how to learn compact binary codes that construct the underlying correlations between heterogeneous features from different modalities. A majority of recent approaches aim at learning hash functions to preserve the pairwise similarities defined by given class labels. However, these methods fail to explicitly explore the discriminative property of class labels during hash function learning. In addition, they usually discard the discrete constraints imposed on the to-be-learned binary codes, and compromise to solve a relaxed problem with quantization to obtain the approximate binary solution. Therefore, the binary codes generated by these methods are suboptimal and less discriminative to different classes. To overcome these drawbacks, we propose a novel cross-modal hashing method, termed discrete cross-modal hashing (DCH), which directly learns discriminative binary codes while retaining the discrete constraints. Specifically, DCH learns modality-specific hash functions for generating unified binary codes, and these binary codes are viewed as representative features for discriminative classification with class labels. An effective discrete optimization algorithm is developed for DCH to jointly learn the modality-specific hash function and the unified binary codes. Extensive experiments on three benchmark data sets highlight the superiority of DCH under various cross-modal scenarios and show its state-of-the-art performance. [ABSTRACT FROM PUBLISHER]

Device-to-device (D2D) communications have recently attracted much attention for the potential capability to improve spectral efficiency (SE) underlaying the existing heterogeneous networks (HetNets). Due to no sophisticated control, D2D-worked user equipments (DUEs) themselves cannot resist eavesdropping or security attacks. It is urgent to maximize the secure capacity for both cellular users and DUEs. This paper formulates the radio resource-allocation problem to maximize the secure capacity of DUEs for D2D communication underlaying HetNets, which consist of high-power nodes (HPNs) and low-power nodes (LPNs). The optimization objective function with transmit bit rate and power constraints, which is nonconvex and hard to directly derive, is first transformed into a matrix form. Then, the equivalent convex form of the optimization problem is derived according to Perron–Frobenius theory. A heuristic iterative algorithm based on the proximal theory is proposed to solve this equivalent convex problem through evaluating the proximal operator of the Lagrange function. Numerical results show that the proposed radio resource-allocation solution significantly improves the secure capacity with a fast convergence speed. [ABSTRACT FROM PUBLISHER]

Low-rank representation (LRR) has been successfully applied in exploring the subspace structures of data. However, in previous LRR-based semi-supervised subspace clustering methods, the label information is not used to guide the affinity matrix construction so that the affinity matrix cannot deliver strong discriminant information. Moreover, these methods cannot guarantee an overall optimum since the affinity matrix construction and subspace clustering are often independent steps. In this paper, we propose a robust semi-supervised subspace clustering method based on non-negative LRR (NNLRR) to address these problems. By combining the LRR framework and the Gaussian fields and harmonic functions method in a single optimization problem, the supervision information is explicitly incorporated to guide the affinity matrix construction and the affinity matrix construction and subspace clustering are accomplished in one step to guarantee the overall optimum. The affinity matrix is obtained by seeking a non-negative low-rank matrix that represents each sample as a linear combination of others. We also explicitly impose the sparse constraint on the affinity matrix such that the affinity matrix obtained by NNLRR is non-negative low-rank and sparse. We introduce an efficient linearized alternating direction method with adaptive penalty to solve the corresponding optimization problem. Extensive experimental results demonstrate that NNLRR is effective in semi-supervised subspace clustering and robust to different types of noise than other state-of-the-art methods. [ABSTRACT FROM PUBLISHER]

The increasing popularity of online social networks (OSNs) has been transforming the dissemination pattern of social video contents. We can utilize the social information propagation pattern to improve the efficiency of social video distribution. In this paper, motivated by the social community classification, we present a social video replication and user request dispatching mechanism in the cloud content delivery network architecture to reduce the system operational cost, while guaranteeing the averaged service latency. Specifically, we first present a community classification method that clusters social users with social relationships, close geolocations, and similar video watching interests into various communities. Then, we conduct a large-scale measurement on a real OSN system to study the diversities of social video propagation and the effectiveness of our communities on smoothing the diversity. Finally, we propose the community-based video replication and request dispatching strategy and formulate it as a constrained optimization problem. Based on a stochastic optimization framework, we derive an online solution and rigorously prove the optimality. We evaluate our algorithm on a real trace under realistic settings and demonstrate that our algorithm can reduce the monetary cost by 30% against traditional approaches with the same service latency. [ABSTRACT FROM AUTHOR]

In this paper, we propose a novel segmentation approach for stereo images using the high-order energy optimization, which utilizes the disparity maps and statistical information of stereo images to enrich the high-order potential functions. To the best of our knowledge, our approach is the first one to formulate the problem of stereo segmentation as a high-order energy optimization problem, which simultaneously segments the foreground objects in left and right images using the proposed high-order potential function. A new method for designing the penalty function in our high-order term is proposed by the corresponding pixels and their neighboring pixels between left and right images. The relationships of stereo correspondence by disparity maps are further employed to enhance the connections between the left and right stereo images. Experimental results demonstrate that the proposed approach can effectively improve the performance of two kinds of stereo segmentation, including the automatic saliency-aware stereocut and the interactive stereo segmentation with user scribbles. [ABSTRACT FROM PUBLISHER]

A novel superpixel extraction algorithm using a higher order energy optimization framework is proposed in this paper. We first adopt the $k$ -means clustering technique to quickly get an initial superpixel result. Then a higher order energy function is employed to optimize and refine these initial superpixels. We use a more general higher order energy function that includes a first-order data term, a second-order smoothness term, and a higher order term. The presegments are employed to provide the prior information of sufficient edges and segment regions for our higher order energy term. According to the texture measurement in different local regions, our algorithm adaptively computes the proper ratios of different energy terms to obtain a better superpixel performance. The experimental results demonstrate that our method using the higher order energy generates better results with well-aligned boundaries and homogeneous effects than the existing superpixel algorithms. [ABSTRACT FROM PUBLISHER]

Supervoxels have been widely used as a preprocessing step to exploit object boundaries to improve the performance of video processing tasks. However, most of the traditional supervoxel algorithms do not perform well in regions with complex textures or weak boundaries. These methods may generate supervoxels with overlapping boundaries. In this paper, we present the novel video supervoxel generation algorithm using partially absorbing random walks to get more accurate supervoxels in these regions. Our spatial–temporal framework is introduced by making full use of the appearance and motion cues, which effectively exploits the temporal consistency in video sequence. Moreover, we build a novel Laplacian optimization structure using two adjacent frames to make our approach more efficient. Experimental results demonstrated that our method achieved better performance than the state-of-the-art supervoxel algorithms. [ABSTRACT FROM PUBLISHER]

We consider the problem of image representation from the perspective of statistical design. Recent studies have shown that images are possibly sampled from a low dimensional manifold despite of the fact that the ambient space is usually very high dimensional. Learning low dimensional image representations is crucial for many image processing tasks such as recognition and retrieval. Most of the existing approaches for learning low dimensional representations, such as principal component analysis (PCA) and locality preserving projections (LPP), aim at discovering the geometrical or discriminant structures in the data. In this paper, we take a different perspective from statistical experimental design, and propose a novel dimensionality reduction algorithm called A-Optimal Projection (AOP). AOP is based on a linear regression model. Specifically, AOP finds the optimal basis functions so that the expected prediction error of the regression model can be minimized if the new representations are used for training the model. Experimental results suggest that the proposed approach provides a better representation and achieves higher accuracy in image retrieval. [ABSTRACT FROM PUBLISHER]

In image analysis, the images are often represented by multiple visual features (also known as multiview features), that aim to better interpret them for achieving remarkable performance of the learning. Since the processes of feature extraction on each view are separated, the multiple visual features of images may include overlap, noise, and redundancy. Thus, learning with all the derived views of the data could decrease the effectiveness. To address this, this paper simultaneously conducts a hierarchical feature selection and a multiview multilabel (MVML) learning for multiview image classification, via embedding a proposed a new block-row regularizer into the MVML framework. The block-row regularizer concatenating a Frobenius norm ( F -norm) regularizer and an \boldsymbol \ell \textbf {2,1} -norm regularizer is designed to conduct a hierarchical feature selection, in which the F -norm regularizer is used to conduct a high-level feature selection for selecting the informative views (i.e., discarding the uninformative views) and the \boldsymbol \ell \textbf {2,1} -norm regularizer is then used to conduct a low-level feature selection on the informative views. The rationale of the use of a block-row regularizer is to avoid the issue of the over-fitting (via the block-row regularizer), to remove redundant views and to preserve the natural group structures of data (via the F -norm regularizer), and to remove noisy features (the \boldsymbol \ell \textbf {2,1} -norm regularizer), respectively. We further devise a computationally efficient algorithm to optimize the derived objective function and also theoretically prove the convergence of the proposed optimization method. Finally, the results on real image datasets show that the proposed method outperforms two baseline algorithms and three state-of-the-art algorithms in terms of classification performance. [ABSTRACT FROM PUBLISHER]

Nowadays, with the continual development of digital capture technologies and social media services, a vast number of media documents are captured and shared online to help attendees record their experience during events. In this paper, we present a method combining semantic inference and multimodal analysis for automatically finding media content to illustrate events using an adaptive probabilistic hypergraph model. In this model, media items are taken as vertices in the weighted hypergraph and the task of enriching media to illustrate events is formulated as a ranking problem. In our method, each hyperedge is constructed using the K-nearest neighbors of a given media document. We also employ a probabilistic representation, which assigns each vertex to a hyperedge in a probabilistic way, to further exploit the correlation among media data. Furthermore, we optimize the hypergraph weights in a regularization framework, which is solved as a second-order cone problem. The approach is initiated by seed media and then used to rank the media documents using a transductive inference process. The results obtained from validating the approach on an event dataset collected from EventMedia demonstrate the effectiveness of the proposed approach. [ABSTRACT FROM PUBLISHER]

Hashing methods are effective in generating compact binary signatures for images and videos. This paper addresses an important open issue in the literature, i.e., how to learn compact hash codes by enhancing the complementarity among different hash functions. Most of prior studies solve this problem either by adopting time-consuming sequential learning algorithms or by generating the hash functions which are subject to some deliberately-designed constraints (e.g., enforcing hash functions orthogonal to one another). We analyze the drawbacks of past works and propose a new solution to this problem. Our idea is to decompose the feature space into a subspace shared by all hash functions and its complementary subspace. On one hand, the shared subspace, corresponding to the common structure across different hash functions, conveys most relevant information for the hashing task. Similar to data de-noising, irrelevant information is explicitly suppressed during hash function generation. On the other hand, in case that the complementary subspace also contains useful information for specific hash functions, the final form of our proposed hashing scheme is a compromise between these two kinds of subspaces. To make hash functions not only preserve the local neighborhood structure but also capture the global cluster distribution of the whole data, an objective function incorporating spectral embedding loss, binary quantization loss, and shared subspace contribution is introduced to guide the hash function learning. We propose an efficient alternating optimization method to simultaneously learn both the shared structure and the hash functions. Experimental results on three well-known benchmarks CIFAR-10, NUS-WIDE, and a-TRECVID demonstrate that our approach significantly outperforms state-of-the-art hashing methods. [ABSTRACT FROM PUBLISHER]

In this paper, we present a novel patch-based match and fusion algorithm by taking account of moving scene in a multiple exposure image sequence using optimization. A uniform iterative approach is developed to match and find the corresponding patches in different exposure images, which are then fused in each iteration. Our approach does not need to align the input multiple exposure images before the fusion process. Considering that the pixel values are affected by various exposure time, we design a new patch-based energy function that will be optimized to improve the matching accuracy. An efficient patch-based exposure fusion approach using the random walker algorithm is developed to preserve the moving objects from the input multiple exposure images. To the best of our knowledge, our algorithm is the first patch-based exposure fusion work to preserve the moving objects of dynamic scenes that does not need the registration process of different exposure images. Experimental results of moving scenes demonstrate that our algorithm achieves visually pleasing fusion results without ghosting artifacts, while the results produced by the state-of-the-art exposure fusion and tone mapping algorithms exhibit different levels of ghosting artifacts. [ABSTRACT FROM PUBLISHER]

This paper presents a new method to compute the dense correspondences between two images by using the energy optimization and the structured patches. In terms of the property of the sparse feature and the principle that nearest sub-scenes and neighbors are much more similar, we design a new energy optimization to guide the dense matching process and find the reliable correspondences. The sparse features are also employed to design a new structure to describe the patches. Both transformation and deformation with the structured patches are considered and incorporated into an energy optimization framework. Thus, our algorithm can match the objects robustly in complicated scenes. Finally, a local refinement technique is proposed to solve the perturbation of the matched patches. Experimental results demonstrate that our method outperforms the state-of-the-art matching algorithms. [ABSTRACT FROM PUBLISHER]

In this paper, we propose a novel energy optimization framework to accurately estimate surface normal and reflectance of an object from an input image sequence. Input images are captured from a fixed viewpoint under varying lighting conditions. In the proposed approach we combine photometric stereo and Retinex constraints into our energy function. To formulate inter-image constraints, shading information is added to the Lambertian model to account for shadows. For intra-image constraints, we moderate the strength of shading smoothness according to shadow mask and normal variations. By minimizing this energy function we are able to recover accurate surface normals and reflectance. Experimental results show that our approach yields more realistic normal map and accurate albedo map than the state-of-the-art uncalibrated photometric stereo algorithms. As for intrinsic image decomposition, results on the real and synthetic scenes show that the proposed approach outperforms previous ones. [ABSTRACT FROM PUBLISHER]

We propose a new graph based hashing method called spectral embedded hashing (SEH) for large-scale image retrieval. We first introduce a new regularizer into the objective function of the recent work spectral hashing to control the mismatch between the resultant hamming embedding and the low-dimensional data representation, which is obtained by using a linear regression function. This linear regression function can be employed to effectively handle the out-of-sample data, and the introduction of the new regularizer makes SEH better cope with the data sampled from a nonlinear manifold. Considering that SEH cannot efficiently cope with the high dimensional data, we further extend SEH to kernel SEH (KSEH) to improve the efficiency and effectiveness, in which a nonlinear regression function can also be employed to obtain the low dimensional data representation. We also develop a new method to efficiently solve the approximate solution for the eigenvalue decomposition problem in SEH and KSEH. Moreover, we show that some existing hashing methods are special cases of our KSEH. Our comprehensive experiments on CIFAR, Tiny-580K, NUS-WIDE, and Caltech-256 datasets clearly demonstrate the effectiveness of our methods. [ABSTRACT FROM PUBLISHER]

Image seam carving algorithm should preserve important and salient objects as much as possible when changing the image size, while not removing the secondary objects in the scene. However, it is still difficult to determine the important and salient objects that avoid the distortion of these objects after resizing the input image. In this paper, we develop a novel depth-aware single image seam carving approach by taking advantage of the modern depth cameras such as the Kinect sensor, which captures the RGB color image and its corresponding depth map simultaneously. By considering both the depth information and the just noticeable difference (JND) model, we develop an efficient JND-based significant computation approach using the multiscale graph cut based energy optimization. Our method achieves the better seam carving performance by cutting the near objects less seams while removing distant objects more seams. To the best of our knowledge, our algorithm is the first work to use the true depth map captured by Kinect depth camera for single image seam carving. The experimental results demonstrate that the proposed approach produces better seam carving results than previous content-aware seam carving methods. [ABSTRACT FROM PUBLISHER]

Recovering a large matrix from a small subset of its entries is a challenging problem arising in many real applications, such as image inpainting and recommender systems. Many existing approaches formulate this problem as a general low-rank matrix approximation problem. Since the rank operator is nonconvex and discontinuous, most of the recent theoretical studies use the nuclear norm as a convex relaxation. One major limitation of the existing approaches based on nuclear norm minimization is that all the singular values are simultaneously minimized, and thus the rank may not be well approximated in practice. In this paper, we propose to achieve a better approximation to the rank of matrix by truncated nuclear norm, which is given by the nuclear norm subtracted by the sum of the largest few singular values. In addition, we develop a novel matrix completion algorithm by minimizing the Truncated Nuclear Norm. We further develop three efficient iterative procedures, TNNR-ADMM, TNNR-APGL, and TNNR-ADMMAP, to solve the optimization problem. TNNR-ADMM utilizes the alternating direction method of multipliers (ADMM), while TNNR-AGPL applies the accelerated proximal gradient line search method (APGL) for the final optimization. For TNNR-ADMMAP, we make use of an adaptive penalty according to a novel update rule for ADMM to achieve a faster convergence rate. Our empirical study shows encouraging results of the proposed algorithms in comparison to the state-of-the-art matrix completion algorithms on both synthetic and real visual datasets. [ABSTRACT FROM AUTHOR]

Recently, much attention has been drawn to the problem of matrix completion, which arises in a number of fields, including computer vision, pattern recognition, sensor network, and recommendation systems. This paper proposes a novel algorithm, named robust alternative minimization (RAM), which is based on the constraint of low rank to complete an unknown matrix. The proposed RAM algorithm can effectively reduce the relative reconstruction error of the recovered matrix. It is numerically easier to minimize the objective function and more stable for large-scale matrix completion compared with other existing methods. It is robust and efficient for low-rank matrix completion, and the convergence of the RAM algorithm is also established. Numerical results showed that both the recovery accuracy and running time of the RAM algorithm are competitive with other reported methods. Moreover, the applications of the RAM algorithm to low-rank image recovery demonstrated that it achieves satisfactory performance. [ABSTRACT FROM AUTHOR]

In this paper we present a new method for simultaneously determining 3-D shape and motion of a nonrigid object from uncalibrated 2-D images without assuming the distribution characteristics. A nonrigid motion can be treated as a combination of a rigid rotation and a nonrigid deformation. To seek accurate recovery of deformable structures, we estimate the probability distribution function of the corresponding features through random sampling, incorporating an established probabilistic model. The fitting between the observation and the projection of the estimated 3-D structure will be evaluated using a Markov chain Monte Carlo based expectation maximization algorithm. Applications of the proposed method to both synthetic and real image sequences are demonstrated with promising results. [ABSTRACT FROM PUBLISHER]