We consider a robust phase retrieval problem that aims to recover a signal from its absolute measurements corrupted with sparse noise. The least absolute deviation (LAD) provides a robust estimation against outliers. However, the corresponding optimization problem is nonconvex. We propose an "unregularized" iterative convexification approach to LAD through a sequence of linear programs (SLP). We provide a non-asymptotic convergence analysis under the standard Gaussian assumption of the measurement vectors. The SLP algorithm, when suitably initialized, linearly converges to the ground truth at optimal sample complexity up to a numerical constant. Furthermore, SLP empirically outperforms existing methods that provide a comparable performance guarantee.

We consider the multivariate max-linear regression problem where the model parameters$ {\beta }_{1},\dotsc, {\beta }_{k}\in \mathbb {R}^{p}$need to be estimated from$n$independent samples of the (noisy) observations$y = \max _{1\leq j \leq k} {\beta }_{j}^{\mathsf {T}} {x} + \mathrm {noise}$. The max-linear model vastly generalizes the conventional linear model, and it can approximate any convex function to an arbitrary accuracy when the number of linear models$k$is large enough. However, the inherent nonlinearity of the max-linear model renders the estimation of the regression parameters computationally challenging. Particularly, no estimator based on convex programming is known in the literature. We formulate and analyze a scalable convex program given by anchored regression (AR) as the estimator for the max-linear regression problem. Under the standard Gaussian observation setting, we present a non-asymptotic performance guarantee showing that the convex program recovers the parameters with high probability. When the$k$linear components are equally likely to achieve the maximum, our result shows a sufficient number of noise-free observations for exact recovery scales as$k^{4}p$up to a logarithmic factor. This sample complexity coincides with that by alternating minimization (Ghosh et al., 2021). Moreover, the same sample complexity applies when the observations are corrupted with arbitrary deterministic noise. We provide empirical results that show that our method performs as our theoretical result predicts, and is competitive with the alternating minimization algorithm particularly in presence of multiplicative Bernoulli noise. Furthermore, we also show empirically that a recursive application of AR can significantly improve the estimation accuracy.

We present an algorithm for the resolution of delayed and overlapping pulses of a common unknown shape from multi-channel measurements. We show that just a few Fourier samples acquired by a Time Encoding Machine (TEM) suffice to solve this challenging problem. This acquisition scheme is desired for ultra-low power applications in wearables, such as EMG skin sensor tattoo. Numerical experiments demonstrate exact recovery of the time delays and Fourier series coefficient of the pulse shape in the noiseless case as predicted by the theory, with acceptable error in the presence of noise.

We consider a continuous-time sparse multichannel blind deconvolution problem. The signal at each channel is expressed as the convolution of a common source signal and its impulse response given as a sparse filter. The objective is to identify these sparse filters from sub-Nyquist samples of channel outputs by leveraging the correlation across channels. We present necessary and sufficient conditions for the unique identification. In particular, the sparse filters should not share a common sparse convolution factor and it is necessary to have 2L or more samples per channel from at least two distinct channels. We also show that L-sparse filters are uniquely identifiable from two channels provided that there are 2L2Fourier measurements per channel, which can be computed from sub-Nyquist samples. Additionally, in the asymptotic of the number of channels, 2L Fourier measurements per channel are sufficient. The results are applicable to the design of multi-receiver, low-rate, sensors in applications such as radar, sonar, ultrasound, and seismic exploration.

We address a low-rank matrix recovery problem where each column of a rank-r matrix X of size (d1,d2) is compressed beyond the point of recovery to size L with L << d1. Leveraging the joint structure between the columns, we propose a method to recover the matrix to within an epsilon relative error in the Frobenius norm from a total of O(r(d1 + d2)\log^6(d1 + d2)/\epsilon^2) observations. This guarantee holds uniformly for all incoherent matrices of rank r. In our method, we propose to use a novel matrix norm called the mixed-norm along with the maximum l2 norm of the columns to design a novel convex relaxation for low-rank recovery that is tailored to our observation model. We also show that our proposed mixed-norm, the standard nuclear norm, and the max-norm are particular instances of convex regularization of low-rankness via tensor norms. Finally, we provide a scalable ADMM algorithm for the mixed-norm based method and demonstrate its empirical performance via large-scale simulations.

Blind gain and phase calibration (BGPC) is a bilinear inverse problem involving the determination of unknown gains and phases of the sensing system, and the unknown signal, jointly. BGPC arises in numerous applications, e.g., blind albedo estimation in inverse rendering, synthetic aperture radar autofocus, and sensor array auto-calibration. In some cases, sparse structure in the unknown signal alleviates the ill-posedness of BGPC. Recently, there has been renewed interest in solutions to BGPC with careful analysis of error bounds. In this paper, we formulate BGPC as an eigenvalue/eigenvector problem and propose to solve it via power iteration, or in the sparsity or joint sparsity case, via truncated power iteration. Under certain assumptions, the unknown gains, phases, and the unknown signal can be recovered simultaneously. Numerical experiments show that power iteration algorithms work not only in the regime predicted by our main results, but also in regimes where theoretical analysis is limited. We also show that our power iteration algorithms for BGPC compare favorably with competing algorithms in adversarial conditions, e.g., with noisy measurement or with a bad initial estimate.

We study the problem of passive imaging through convolutive channels. A scene is illuminated with an unknown, unstructured source, and the measured response is the convolution of this source with multiple channel responses, each of which is time-limited. Spectral methods based on the commutativity of convolution, first proposed and analyzed in the 1990s, provide an elegant mathematical framework for attacking this problem. However, these now classical methods are very sensitive to noise, especially when working from relatively small sample sizes. In this paper, we show that a linear subspace model on the coefficients of the impulse responses of the channels can make this problem well-posed. We derive nonasymptotic error bounds for the generic subspace model by analyzing the spectral gap of the cross-correlation (CC) matrix of the channels relative to the perturbation introduced by noise. Numerical results show that this modified spectral method offers significant improvements over the classical method and outperforms other competing methods for multichannel blind deconvolution.

Compressed sensing is provided a data-acquisition paradigm for sparse signals. Remarkably, it has been shown that the practical algorithms provide robust recovery from noisy linear measurements acquired at a near optimal sampling rate. In many real-world applications, a signal of interest is typically sparse not in the canonical basis but in a certain transform domain, such as wavelets or the finite difference. The theory of compressed sensing was extended to the analysis sparsity model, but known extensions are limited to the specific choices of sensing matrix and sparsifying transform. In this paper, we propose a unified theory for robust recovery of sparse signals in a general transform domain by convex programming. In particular, our results apply to the general acquisition and sparsity models and show how the number of measurements for recovery depends on properties of measurement and sparsifying transforms. Moreover, we also provide extensions of our results to the scenarios where the atoms in the transform have varying incoherence parameters and the unknown signal exhibits a structured sparsity pattern. In particular, for the partial Fourier recovery of sparse signals over a circulant transform, our main results suggest a uniformly random sampling. Numerical results demonstrate that the variable density random sampling by our main results provides a superior recovery performance over the known sampling strategies.

We consider the multichannel blind deconvolution problem where we observe the output of multiple channels that are all excited with the same unknown input. From these observations, we wish to estimate the impulse responses of each of the channels. We show that this problem is well-posed if the channels follow a bilinear model where the ensemble of channel responses is modeled as lying in a low-dimensional subspace but with each channel modulated by an independent gain. Under this model, we show how the channel estimates can be found by minimizing a quadratic function over a non-convex set. We analyze two methods for solving this non-convex program, and provide performance guarantees for each. The first is a method of alternating eigenvectors that breaks the program down into a series of eigenvalue problems. The second is a truncated power iteration, which can roughly be interpreted as a method for finding the largest eigenvector of a symmetric matrix with the additional constraint that it adheres to our bilinear model. As with most non-convex optimization algorithms, the performance of both of these algorithms is highly dependent on having a good starting point. We show how such a starting point can be constructed from the channel measurements. Our performance guarantees are non-asymptotic, and provide a sufficient condition on the number of samples observed per channel in order to guarantee channel estimates of certain accuracy. Our analysis uses a model with a “generic” subspace that is drawn at random, and we show the performance bounds hold with high probability. Mathematically, the key estimates are derived by quantifying how well the eigenvectors of certain random matrices approximate the eigenvectors of their mean. We also present a series of numerical results demonstrating that the empirical performance is consistent with the presented theory.

Compressed sensing of simultaneously sparse and low-rank matrices enables recovery of sparse signals from a few linear measurements of their bilinear form. One important question is how many measurements are needed for a stable reconstruction in the presence of measurement noise. Unlike conventional compressed sensing for sparse vectors, where convex relaxation via the ℓ1-norm achieves near-optimal performance, for compressed sensing of sparse low-rank matrices, it has been shown recently that convex programmings using the nuclear norm and the mixed norm are highly suboptimal even in the noise-free scenario. We propose an alternating minimization algorithm called sparse power factorization (SPF) for compressed sensing of sparse rank-one matrices. For a class of signals whose sparse representation coefficients are fast-decaying, SPF achieves stable recovery of the rank-one matrix formed by their outer product and requires number of measurements within a logarithmic factor of the information-theoretic fundamental limit. For the recovery of general sparse low-rank matrices, we propose subspace-concatenated SPF (SCSPF), which has analogous near-optimal performance guarantees to SPF in the rank-one case. Numerical results show that SPF and SCSPF empirically outperform convex programmings using the best known combinations of mixed norm and nuclear norm.

Subsampled blind deconvolution is the recovery of two unknown signals from samples of their convolution. To overcome the ill-posedness of this problem, solutions based on priors tailored to specific practical application have been developed. In particular, sparsity models have provided promising priors. However, in spite of the empirical success of these methods in many applications, existing analyses are rather limited in two main ways: by disparity between the theoretical assumptions on the signal and/or measurement model versus practical setups; or by failure to provide a performance guarantee for parameter values within the optimal regime defined by the information theoretic limits. In particular, it has been shown that a naive sparsity model is not a strong enough prior for identifiability in the blind deconvolution problem. Instead, in addition to sparsity, we adopt a conic constraint, which enforces spectral flatness of the signals. Under this prior together with random dictionary models, we show that the unknown sparse signals can be recovered from samples of their convolution at a rate scaling near optimally with the problem parameters. We also propose an iterative algorithm that is guaranteed to provide robust recovery at the same near optimal sample complexity provided that certain projection steps in the algorithm are successful. In our analysis, we have not verified the success of these projection steps, but these steps are inactive with high probability. Numerical results show the empirical performance of the iterative algorithm agrees with the performance guarantee.

Bilinear inverse problems (BIPs), the resolution of two vectors given their image under a bilinear mapping, arise in many applications. Without further constraints, BIPs are usually ill-posed. In practice, the properties of natural signals are exploited to solve BIPs. For example, subspace constraints or sparsity constraints are imposed to reduce the search space. These approaches have shown some success in practice. However, there are few results on uniqueness in BIPs. For most BIPs, the fundamental question of under what condition the problem admits a unique solution is yet to be answered. For example, blind gain and phase calibration (BGPC) is a structured BIP, which arises in many applications, including inverse rendering in computational relighting (albedo estimation with unknown lighting), blind phase and gain calibration in sensor array processing, and multichannel blind deconvolution (MBD). It is interesting to study the uniqueness of such problems. In this paper, we define identifiability of a BIP up to a group of transformations. We derive necessary and sufficient conditions for such identifiability, i.e., the conditions under which the solutions can be uniquely determined up to the transformation group. These conditions take the form of dividing the identifiability of the pair of unknown variables into the individual identifiability of each variable. Although verifying these individual conditions requires problem-specific procedures, this framework is universally applicable to all BIPs. Applying these results to BGPC, we derive sufficient conditions for unique recovery under several scenarios, including subspace, joint sparsity, and sparsity models. For BGPC with joint sparsity or sparsity constraints, we develop a procedure to compute the transformation groups corresponding to inherent ambiguities. We also give necessary conditions in the form of tight lower bounds on sample complexities, and demonstrate the tightness of these bounds by numerical experiments. The results for BGPC not only demonstrate the application of the proposed general framework for identifiability analysis, but are also of interest in their own right.

Blind deconvolution (BD) arises in many applications. Without assumptions on the signal and the filter, BD does not admit a unique solution. In practice, subspace or sparsity assumptions have shown the ability to reduce the search space and yield the unique solution. However, existing theoretical analysis on uniqueness in BD is rather limited. In an earlier paper, we provided the first algebraic sample complexities for BD that hold for Lebesgue almost all bases or frames. We showed that for BD of a pair of vectors in ℂn, with subspace constraints of dimensions m1and m2, respectively, a sample complexity of n ≥ m1m2is sufficient. This result is suboptimal, since the number of degrees of freedom is merely m1+ m2- 1. We provided analogous results, with similar suboptimality, for BD with sparsity or mixed subspace and sparsity constraints. In this paper, taking advantage of the recent progress on the information-theoretic limits of unique low-rank matrix recovery, we finally bridge this gap, and derive an optimal sample complexity result for BD with generic bases or frames. We show that for BD of an arbitrary pair (respectively, all pairs) of vectors in ℂn, with sparsity constraints of sparsity levels s1 and s2, a sample complexity of n > s1+ s2[respectively, n > 2(s1+s2)] is sufficient. We also present analogous results for BD with subspace constraints or mixed constraints, with the subspace dimension replacing the sparsity level. Last but not least, in all the above scenarios, if the bases or frames follow a probabilistic distribution specified in this paper, the recovery is not only unique, but also stable against small perturbations in the measurements, under the same sample complexities.

While the recent theory of compressed sensing provides an opportunity to overcome the Nyquist limit in recovering sparse signals, a solution approach usually takes the form of an inverse problem of an unknown signal, which is crucially dependent on specific signal representation. In this paper, we propose a drastically different two-step Fourier compressive sampling framework in a continuous domain that can be implemented via measurement domain interpolation, after which signal reconstruction can be done using classical analytic reconstruction methods. The main idea originates from the fundamental duality between the sparsity in the primary space and the low-rankness of a structured matrix in the spectral domain, showing that a low-rank interpolator in the spectral domain can enjoy all of the benefits of sparse recovery with performance guarantees. Most notably, the proposed low-rank interpolation approach can be regarded as a generalization of recent spectral compressed sensing to recover large classes of finite rate of innovations (FRI) signals at a near-optimal sampling rate. Moreover, for the case of cardinal representation, we can show that the proposed low-rank interpolation scheme will benefit from inherent regularization and an optimal incoherence parameter. Using a powerful dual certificate and the golfing scheme, we show that the new framework still achieves a near-optimal sampling rate for a general class of FRI signal recovery, while the sampling rate can be further reduced for a class of cardinal splines. Numerical results using various types of FRI signals confirm that the proposed low-rank interpolation approach offers significantly better phase transitions than conventional compressive sampling approaches.

Electricity theft is a major concern for utilities all over the world, and leads to billions of dollars in losses every year. Although improving the communication capabilities between consumer smart meters and utilities can enable many smart grid features, these communications can be compromised in ways that allow an attacker to steal electricity. Such attacks have recently begun to occur, so there is a real and urgent need for a framework to defend against them. In this paper, we make three major contributions. First, we develop what is, to our knowledge, the most comprehensive classification of electricity theft attacks in the literature. These attacks are classified based on whether they can circumvent security measures currently used in industry, and whether they are possible under different electricity pricing schemes. Second, we propose a theft detector based on Kullback-Leibler (KL) divergence to detect cleverly-crafted electricity theft attacks that circumvent detectors proposed in related work. Finally, we evaluate our detector using false data injections based on real smart meter data. For the different attack classes, we show that our detector dramatically mitigates electricity theft in comparison to detectors in prior work.

Tremendous efforts have been made to study the theoretical and algorithmic aspects of sparse recovery and low-rank matrix recovery. This paper establishes (near) optimal sample complexities for stable matrix recovery without constants or log factors. We treat sparsity, low-rankness, and other parsimonious structures within the same framework: constraint sets that have small covering numbers or Minkowski dimensions, which include notoriously challenging cases such as simultaneously sparse and low-rank matrices. We consider three types of random measurement matrices (unstructured, rank-1, and symmetric rank-1 matrices), following probability distributions that satisfy some mild conditions. In all these cases, we prove a fundamental achievability result - the recovery of matrices with parsimonious structures, using an optimal (or near optimal) number of measurements, is stable with high probability.

Blind deconvolution (BD), the resolution of a signal and a filter given their convolution, arises in many applications. Without further constraints, BD is ill-posed. In practice, subspace or sparsity constraints have been imposed to reduce the search space, and have shown some empirical success. However, the existing theoretical analysis on uniqueness in BD is rather limited. In an effort to address the still open question, we derive sufficient conditions under which two vectors can be uniquely identified from their circular convolution, subject to subspace or sparsity constraints. These sufficient conditions provide the first algebraic sample complexities for BD. We first derive a sufficient condition that applies to almost all bases or frames. For BD of vectors in ℂn, with two subspace constraints of dimensions m1and m2, the required sample complexity is n ≥ m1m2. Then, we impose a sub-band structure on one basis, and derive a sufficient condition that involves a relaxed sample complexity n≥ m1+m2-1, which we show to be optimal. We present the extensions of these results to BD with sparsity constraints or mixed constraints, with the sparsity level replacing the subspace dimension. The cost for the unknown support in this case is an extra factor of 2 in the sample complexity.

Compressed sensing enables universal, simple, and reduced-cost acquisition by exploiting a sparse signal model. Most notably, recovery of the signal by computationally efficient algorithms is guaranteed for certain random measurement models, which satisfy the so-called isotropy property. However, in real-world applications, this property is often not satisfied. We propose two related changes in the existing framework for the anisotropic case: (i) a generalized RIP called the restricted biorthogonality property (RBOP); and (ii) correspondingly modified versions of existing greedy pursuit algorithms, which we call oblique pursuits. Oblique pursuits provide recovery guarantees via the RBOP without requiring the isotropy property; hence, these recovery guarantees apply to practical acquisition schemes. Numerical results show that oblique pursuits also perform better than their conventional counterparts.

In this correspondence, a corrected version of the convergence analysis given by Lee and Bresler in the above titled paper (ibid., vol. 56, no. 9, pp. 4402-4416, Sep. 2010) is presented.

Compressed sensing is a new data acquisition paradigm enabling universal, simple, and reduced-cost acquisition, by exploiting a sparse signal model. Most notably, recovery of the signal by computationally efficient algorithms is guaranteed for certain randomized acquisition systems. However, there is a discrepancy between the theoretical guarantees and practical applications. In applications, including Fourier imaging in various modalities, the measurements are acquired by inner products with vectors selected randomly (sampled) from a frame. Currently available guarantees are derived using the so-called restricted isometry property (RIP), which has only been shown to hold under ideal assumptions. For example, the sampling from the frame needs to be independent and identically distributed with the uniform distribution, and the frame must be tight. In practice though, one or more of the ideal assumptions are typically violated and none of the RIP-based guarantees applies. Motivated by this discrepancy, we propose two related changes in the existing framework: 1) a generalized RIP called the restricted biorthogonality property (RBOP); and 2) correspondingly modified versions of existing greedy pursuit algorithms, which we call oblique pursuits. Oblique pursuits are guaranteed using the RBOP without requiring ideal assumptions; hence, the guarantees apply to practical acquisition schemes. Numerical results show that oblique pursuits also perform competitively with, or sometimes better than their conventional counterparts.

We propose robust and efficient algorithms for the joint sparse recovery problem in compressed sensing, which simultaneously recover the supports of jointly sparse signals from their multiple measurement vectors obtained through a common sensing matrix. In a favorable situation, the unknown matrix, which consists of the jointly sparse signals, has linearly independent nonzero rows. In this case, the MUltiple SIgnal Classification (MUSIC) algorithm, originally proposed by Schmidt for the direction of arrival estimation problem in sensor array processing and later proposed and analyzed for joint sparse recovery by Feng and Bresler, provides a guarantee with the minimum number of measurements. We focus instead on the unfavorable but practically significant case of rank defect or ill-conditioning. This situation arises with a limited number of measurement vectors, or with highly correlated signal components. In this case, MUSIC fails and, in practice, none of the existing methods can consistently approach the fundamental limit. We propose subspace-augmented MUSIC (SA-MUSIC), which improves on MUSIC such that the support is reliably recovered under such unfavorable conditions. Combined with a subspace-based greedy algorithm, known as Orthogonal Subspace Matching Pursuit, which is also proposed and analyzed in this paper, SA-MUSIC provides a computationally efficient algorithm with a performance guarantee. The performance guarantees are given in terms of a version of the restricted isometry property. In particular, we also present a non-asymptotic perturbation analysis of the signal subspace estimation step, which has been missing in the previous studies of MUSIC.

In this paper, we address compressed sensing of a low-rank matrix posing the inverse problem as an approximation problem with a specified target rank of the solution. A simple search over the target rank then provides the minimum rank solution satisfying a prescribed data approximation bound. We propose an atomic decomposition providing an analogy between parsimonious representations of a sparse vector and a low-rank matrix and extending efficient greedy algorithms from the vector to the matrix case. In particular, we propose an efficient and guaranteed algorithm named atomic decomposition for minimum rank approximation (ADMiRA) that extends Needell and Tropp's compressive sampling matching pursuit (CoSaMP) algorithm from the sparse vector to the low-rank matrix case. The performance guarantee is given in terms of the rank-restricted isometry property (R-RIP) and bounds both the number of iterations and the error in the approximate solution for the general case of noisy measurements and approximately low-rank solution. With a sparse measurement operator as in the matrix completion problem, the computation in ADMiRA is linear in the number of measurements. Numerical experiments for the matrix completion problem show that, although the R-RIP is not satisfied in this case, ADMiRA is a competitive algorithm for matrix completion.

Recht, Fazel, and Parrilo provided an analogy between rank minimization and ¿0-norm minimization. Subject to the rank-restricted isometry property, nuclear norm minimization is a guaranteed algorithm for rank minimization. The resulting semidefinite formulation is a convex problem but in practice the algorithms for it do not scale well to large instances. Instead, we explore missing terms in the analogy and propose a new algorithm which is computationally efficient and also has a performance guarantee. The algorithm is based on the atomic decomposition of the matrix variable and extends the idea in the CoSaMP algorithm for ¿0-norm minimization. Combined with the recent fast low rank approximation of matrices based on randomization, the proposed algorithm can efficiently handle large scale rank minimization problems.

There are various conditions on the CS matrix for unique and stable recovery. These include universality, or spark, and UUP. Furthermore, quantitative bounds on the stability depend on related properties of the CS matrix. The construction of good CS matrices - satisfying the various properties - is key to successful practical applications of compressive sensing. Unfortunately, verifying the satisfiability of any of these properties for a given CS matrix involves infeasible combinatorial search. Our methods use i\ and semidefinite relaxation into a convex problem. Given a set of candidate CS matrices, our approach provides tools for the selection of good CS matrices with verified and quantitatively favorable performance.

In this paper, we propose the block-coordinate Gauss- Newton/regression method in order to conduct a correlation-based registration considering the intensity difference between images in the presence of outlier objects. In the proposed method, the parameters are decomposed into two blocks, one of which is for the spatial registration and the other for the intensity compensation. The two blocks are sequentially updated by the Gauss-Newton update and the polynomial regression, respectively. Because of the separated blocks, we can perform a joint optimization with low computational complexity and high implementation flexibility. For example, we apply separately appropriate scaling techniques to the parameter blocks for a stable and fast convergence of the algorithm. Furthermore, we apply the constrained monotone regression with a robust outlier detection scheme for the intensity compensation block. From numerical results, it is shown that the proposed algorithm more effectively performs a correlation-based registration considering the intensity difference alleviating the influence of the outlier objects compared to the traditional registration algorithms that perform the joint optimization.

In this paper, the block-coordinate Gauss-Newton/regression method is proposed to jointly optimize the spatial registration and the intensity compensation. Here, the intensity compensation is conducted constructing a polynomial regression model, which enables the detection of occluded regions as outliers. Based on the block-coordinate method, we separate the parameter update into two steps for registration and compensation, respectively. Hence, we can perform a joint optimization with low computational complexities, and can apply an appropriate scaling technique to the parameters to be updated for a stable and fast convergence of the algorithm. Excluding outliers, we can successfully align images compensating the intensity differences.

In this paper, a comparametric exposure compensation is conducted using a nonparametric estimator: empirical conditional mean. The Nadaraya-Watson estimator is used to smooth the empirical conditional mean curve especially for the case of small number of samples. The performance of the estimator is compared with those of the polynomial and piecewise-linear fittings. Designing the Nadaraya-Watson estimator is very simple and achieves lower errors than the fitting cases, which require a heavy computational burden of solving equations, without worry about the singular matrix case

In order to reduce the blocking artifact in the Joint Photographic Experts Group (JPEG)-compressed images, a new noniterative postprocessing algorithm is proposed. The algorithm consists of a two-step operation: low-pass filtering and then predicting. Predicting the original image from the low-pass filtered image is performed by using the predictors, which are constructed based on a broken line regression model. The constructed predictor is a generalized version of the projector onto the quantization constraint set, or the narrow quantization constraint set. We employed different predictors depending on the frequency components in the discrete cosine transform (DCT) domain since each component has different statistical properties. Further, by using a simple classifier, we adaptively applied the predictors depending on the local variance of the DCT block. This adaptation enables an appropriate blurring depending on the smooth or detail region, and shows improved performance in terms of the average distortion and the perceptual view. For the major-edge DCT blocks, which usually suffer from the ringing artifact, the quality of fit to the regression model is usually not good. By making a modification of the regression model for such DCT blocks, we can also obtain a good perceptual view. The proposed algorithm does not employ any sophisticated edge-oriented classifiers and nonlinear filters. Compared to the previously proposed algorithms, the proposed algorithm provides comparable or better results with less computational complexity.

This letter proposes a new asymmetric watermarking system. In the proposed system, a linear transformation A is applied to the primitive key u to form the private encoding key Au and the public decoding key A/sup -t/u, where -t denotes inverse transpose. The transformation mostly cancels out when the decoding key is correlated to watermarked signal containing the encoding key, which is possibly contaminated with noise. Our analysis shows that this simple scheme provides not only reliability in watermark detection but also security from any attempts to identify or erase the "encoding" key. We also address the issue of selecting a good transformation matrix. The proposed system can be made fit for each application by properly designing the transform.

In this letter, we propose a new asymmetric watermarking system which can accommodate many embedding watermarks but needs only one reference watermark for detection. Such a system is useful in averting attacks that seek to estimate the embedding watermark. In the proposed system, the phase of the reference watermark is shifted randomly (clockwise or counterclockwise) in the discrete Fourier transform domain to make embedding watermarks. They are correlated with one another and have the same correlation with the reference one. We also address how to select the design parameters.

In clustering the training vectors, we may consider an algorithm, which tries to find empirically optimal representative vectors that achieve the empirical minimum to inductively design optimal representative vectors yielding the true optimum. In order to evaluate the performance of the representative vectors, we may observe the empirical minimum with respect to the training ratio, the ratio of the training sequence size to the number of representative vectors. In this paper, the convergence rates of the expectations of the empirical minimum and the validating errors are observed with respect to the training ratio. When enhancing the noisy particle images, which are obtained from the transmission electron microscopy, the theoretical analysis is employed to discuss the performance in conjunction with the overfitting property.

In order to design an efficient blind watermarking scheme, Eggers, et al. (2000) proposed the scalar Costa scheme (SCS). However, SCS, which is based on the uniform scalar quantizer, is vulnerable to the amplitude modification. In this paper, we propose an amplitude-modification resilient watermarking scheme, which is a modified SCS based on the A-law companding. By using the A-law companding, resilience against the amplitude modification can be achieved.

In this paper, we propose a new postprocessing algorithm that reduces the blocking artifacts in low-rate coded images. It consists of two-step operations: low-pass £ltering and image estimation. The latter makes an estimation of the original image from the £ltered image based on regression functions. Regression functions for the JPEG-coded real images are numerically evaluated from a training set, and their piecewise linear approximation are used for the estimation. This approximate unbiased estimator is applied adaptively, depending on the DCT coef£cients. This proposed approach is a generalization of the existing methods as QCS [6] and NQCS [3], [4] can be regarded as the same type that employ biased estimators. Simulation results show that the new algorithm outperforms the existing methods in both objective and subjective qualities.