Image Deconvolution via Superfast Inversion of a Class of Two-Level Toeplitz Matrices. C. Turnes, D. Balcan, and J. Romberg. In IEEE ICIP, Orlando, FL, USA, 2012.[pdf]
In this work we present an efﬁcient method to recover images that have been corrupted by a certain class of image ﬁlters. For this class of ﬁlters, the image degradation process is described by a linear system of equations involving a two-level Toeplitz matrix with triangular structure on either the block or subblock level. This type of structure has algebraic properties that allow us to adapt "superfast" methods for Toeplitz matrix inversion to the two-level case. Our novel two-level superfast algorithm performs the majority of its calculation with the Fast Fourier Transform and allows us to invert an NxN matrix in O(N log N) with reasonable overhead constant. To demonstrate the power of the algorithm we deblur severely corrupted images in short execution times.
Generalized Subgraph Preconditioners for Large-Scale Bundle Adjustment.
Y.-D. Jian, D. C. Balcan, F. Dellaert.
In ICCV, Barcelona, Spain, 2011.[pdf]
We present a generalized subgraph preconditioning (GSP) technique to solve large-scale bundle adjustment problems efficiently. In contrast with previous work which uses either direct or iterative methods as the linear solver, GSP combines their advantages and is significantly faster on large datasets. Similar to , the main idea is to identify a sub-problem (subgraph) that can be solved efficiently by sparse factorization methods and use it to build a preconditioner for the conjugate gradient method. The difference is that GSP is more general and leads to much more effective preconditioners. We design a greedy algorithm to build subgraphs which have bounded maximum clique size in the factorization phase, and also result in smaller condition numbers than standard preconditioning techniques. When applying the proposed method to the “bal” datasets , GSP displays promising performance.
Extended version appears as book chapter in Outdoor Large-Scale Real-World Scene Analysis, Dagstuhl Reports, 2012. [pdf]
Guaranteeing Convergence of Iterative Skewed Voting Algorithms for Image Segmentation.
D. Balcan, G. Srinivasa, M. Fickus, J. Kovačević. In Journal of Applied and Computational Harmonic Analysis, vol. 33 (2), pp. 300-308, Sep. 2012. [arXiv]
In this paper we provide rigorous proof for the convergence of an iterative
voting-based image segmentation algorithm called Active Masks. Active Masks
(AM) was proposed to solve the challenging task of delineating punctate
patterns of cells from fluorescence microscope images. Each iteration of AM
consists of a linear convolution composed with a nonlinear thresholding; what
makes this process special in our case is the presence of additive terms whose
role is to "skew" the voting when prior information is available. In real-world
implementation, the AM algorithm always converges to a fixed point. We study
the behavior of AM rigorously and present a proof of this convergence. The key
idea is to formulate AM as a generalized (parallel) majority cellular
automaton, adapting proof techniques from discrete dynamical systems.
Convergence Behavior of the Active Mask Segmentation Algorithm.
D. Balcan, G. Srinivasa, M. Fickus, J. Kovačević.
In IEEE ICASSP, Dallas, TX, 2010.[pdf]
We study the
convergence behavior of the ActiveMask (AM) framework, originally designed for segmenting punctate image patterns. AM combines the flexibility of traditional active contours, the statistical
modeling power of region-growing methods, and the computational efficiency of multiscale and multiresolution methods. Additionally, it achieves experimental convergence to zero-change (fixed point) configurations, a desirable property for segmentation algorithms. At its a core lies a voting-based distributing function which behaves as a majority cellular automaton. This paper proposes an empirical measure correlated to the convergence behavior of AM, and provides sufficient theoretical conditions on the smoothing filter operator to enforce convergence.
- Point Coding: Sparse Image Representation with
Adaptive Shiftable-Kernel Dictionaries. D. Balcan, M. S. Lewicki. In SPARS 2009.[pdf]
This paper addresses the problem of adaptively
deriving optimally sparse image representations, using an dictionary
composed of shiftable kernels. Algorithmic advantages of
our solution make possible the computation of an approximately
shift-invariant adaptive image representation. Learned kernels
can have different sizes and adapt to different scales. Coefficient
extraction uses a fast implementation of Matching Pursuit with
essentially logarithmic cost per iteration. Dictionary update is
performed by solving a structured least-squares problem either
by algebraic characterization of pseudoinverses of structured
matrices, or by superfast interpolation methods. Kernels learned
from natural images display expected 2D Gabor aspect (localization
in orientation and frequency), as well as other structures
commonly occurring in images (e.g., curved edges, or cross
patterns), while when applied to newspaper text images, kernels
tend to reproduce printed symbols or groups thereof.
- Adaptive coding of images via
Multiresolution ICA. D. Balcan, M. S. Lewicki. In IEEE ICASSP, Taipei, Taiwan, 2009.[pdf]
(MR) representations have been very successful in
image encoding, due to both their algorithmic performance and coding
efficiency. However these transforms are fixed, suggesting that
coding efficiency could be further improved if a multiresolution code
could be adapted to a specific signal class. Among adaptive coding
methods, independent component analysis (ICA) provides the
best linear code by finding a linear transform with maximally independent
coefficients, given a specific signal distribution. This technique,
however, scales poorly with the dimensionality of the data,
and has been ill-suited for large-scale image coding. We propose
a hybrid method (multi-resolution ICA) which derives an ICA basis
for each subband space produced by a given MR transform over
the image class. We find that this method produces a significantly
more efficient code compared to the MR transform alone. We provide
both quantitative and qualitative assessments of coding performance,
and illustrate improvement over standard (i.e., non-adaptive)
wavelet-based representations such as that used in JPEG2000.
to the Discrete Fourier Transform. D. Balcan, A. Sandryhaila, J. Gross, and M. Püschel. In IEEE ICASSP, Las Vegas, NV,
well-known that the discrete Fourier transform (DFT) of a finite
length discrete-time signal samples the discrete-time Fourier
transform of the same signal at equidistant points on the unit circle.
Hence, as the signal length goes to infinity, the DFT approaches
the DTFT. Associated with the DFT are circular convolution and a
periodic signal extension. In this paper we identify a large class
of alternatives to the DFT using the theory of polynomial algebras.
Each of these Fourier transforms approaches the DTFT just as the
DFT does, but has its own signal extension and notion of convolution.
Further, these Fourier transforms have Vandermonde structure,
which enables their fast computation. We provide a few experimental
examples that confirm our theoretical results.
- Robust coding over
noisy overcomplete channels. E. Doi, D. C. Balcan, and M. S. Lewicki. In IEEE Trans. Image Proc., vol. 2, no.
16, Feb. 2007, pp. 442-452.[pdf]
address the problem of robust coding in which the
signal information should be preserved in spite of intrinsic noise
in the representation. We present a theoretical analysis for 1- and
2-D cases and characterize the optimal linear encoder and decoder
in the mean-squared error sense. Our analysis allows for an arbitrary
number of coding units, thus including both under- and
over-complete representations, and provides insights into optimal
coding strategies. In particular, we show how the form of the code
adapts to the number of coding units and to different data and
noise conditions in order to achieve robustness. We also present
numerical solutions of robust coding for high-dimensional image
data, demonstrating that these codes are substantially more robust
than other linear image coding methods such as PCA, ICA, and
- Statistical Inference
of Missing Speech Data in the ICA Domain. J. Rosca, T. Gerkmann, D.C. Balcan.
In IEEE ICASSP, Toulouse, France, 2006.[pdf]
address the problem of speech estimation as statistical estimation
with “missing” data in the independent component analysis (ICA) domain.
Missing components are substituted by values drawn from “similar” data
a multi-faceted ICA representation of the complete data. The paper
the algorithm for the inference of missing data in the case of a fixed
of missing data. We apply our approach to the problem of bandwidth
or where speech is degraded by a fixed filtering process and show the
capability of the algorithm to reconstruct fine missing details of the
data with little artifacts. The evaluation is done using objective
measures on speech samples from the NTT database.
- Independent Component Analysis for
Speech Enhancement with Missing TF Content. D.C. Balcan, J. Rosca.
In ICA, Charleston, SC, USA, 2006.[pdf]
address the problem of Speech Enhancement in a setting
where parts of the time-frequency content of the speech signal are
In telephony, speech is band-limited and the goal is to reconstruct a
wide-band version of the observed data. Quite differently, in Blind
Separation scenarios, information about a source can be masked by noise
or other sources. These masked components are “gaps” or missing source
values to be “filled in”. We propose a framework for unitary treatment
these problems, which is based on a relatively simple “spectrum
procedure. The main idea is to use Independent Component Analysis
as an adaptive, data-driven, linear representation of the signal in the
speech frame space, and then apply a vector-quantization-based matching
procedure to reconstruct each frame. We analyze the performance of
the reconstruction with objective quality measures such as log-spectral
distortion and Itakura-Saito distance.
- A Theoretical Analysis
of Robust Coding over Noisy Overcomplete Channels. E. Doi, D.C. Balcan, M.S. Lewicki.
In NIPS, Vancouver, BC, Canada, 2005.[pdf]
sensory systems are faced with the problem of encoding a
high-fidelity sensory signal with a population of noisy, low-fidelity
This problem can be expressed in information theoretic terms as
coding and transmitting a multi-dimensional, analog signal over a set
noisy channels. Previously, we have shown that robust, overcomplete
codes can be learned by minimizing the reconstruction error with a
on the channel capacity. Here, we present a theoretical analysis
that characterizes the optimal linear coder and decoder for one- and
data. The analysis allows for an arbitrary number of coding
units, thus including both under- and over-complete representations,
provides a number of important insights into optimal coding strategies.
In particular, we show how the form of the code adapts to the number
of coding units and to different data and noise conditions to achieve
We also report numerical solutions for robust coding of highdimensional
image data and show that these codes are substantially more
robust compared against other image codes such as ICA and wavelets.