This year, the international colloquium of LIX (Ecole Polytechnique) focuses on the emerging trends and challenges of the foundations of the cross-disciplinary area of visual computing. Visual computing encompasses computational geometry, computer graphics, machine vision and learning (just to name a few), and relies at its very heart on information geometry. Visual computing is underpinning major industrial applications as attested recently by the emerging fields of computational photography, 3D cinematography and advanced biomedical imaging.
For fairness, the CS part was inspired by Matthew Moravec et al. "Compressive Phase Retrieval", Wavelets XII, SPIE 6701, No. 1. (2007)
Compressed sensing allows perfect recovery of a signal that is known to be sparse in some basis using only a small number of measurements. The results in the literature have focused on the asymptotics of how many samples are required and the probability of making an error for a fixed batch of samples. We investigate an alternative scenario where observations are available in sequence and can be stopped as soon as there is reasonable certainty of correct reconstruction. For the random Gaussian ensemble we show that a simple stopping rule gives the absolute minimum number of observations required for exact recovery, with probability one. However, for other ensembles like Bernoulli or Fourier, this is no longer true, and the rule is modified to trade off delay in stopping and probability of error. We also describe a stopping rule for the nearsparse case which tells when enough observations are made to reach a desired tolerance in reconstruction. Sequential approach to compressed sensing involves the solution of a sequence of linear programs, and we outline how this sequence can be solved efficiently.
Compressed Sensing seeks to capture a discrete signal x element of R^N with a small number n of linear measurements. The information captured about x from such measurements is given by the vector y = \phi x element of R^n where is an n x N matrix. The best matrices, from the viewpoint of capturing sparse or compressible signals, are generated by random processes, e.g. their entries are given by i.i.d. Bernoulli or Gaussian random variables. The information y holds about x is extracted by a decoder mapping R^n into R^N. Typical decoders are based on l1-minimization and greedy pursuit. The present paper studies the performance of decoders based on thresholding. For quite general random families of matrices , decoders are constructed which are instance-optimal in probability by which we mean the following. If x is any vector in R^N, then with high probability applying \delta to y = \phi x gives a vector x :=\Delta (y) such that ||x-x^-|| less than C_0 \sigma_k(x)_l2 for all k less than a n / logN provided a is suciently small (depending on the probability of failure). Here \sigma_k(x)_l2 is the error that results when x is approximated by the k sparse vector which equals x in its k largest coordinates and is otherwise zero. It is also shown that results of this type continue to hold even if the measurement vector y is corrupted by additive noise: y = \phi x + e where e is some noise vector. In this case \sigma_k(x)_l2 is replaced by \sigma_k(x)_l2 + ||e||_l2 .
L1Packv2 is a Mathematica package that contains a number of algorithms that can be used for the minimization of an $\ell_1$-penalized least squares functional. The algorithms can handle a mix of penalized and unpenalized variables. Several instructive examples are given. Also, an implementation that yields an exact output whenever exact data are given is provided.
The central framework for signal recovery in compressive sensing is l_1 norm minimization. In recent years, tremendous progress has been made on algorithms, typically based on some kind of gradient descent or Newton iterations, for performing l_1 norm minimization. These algorithms, however, are for the most part “static”: they focus on finding the solution for a fixed set of measurements. In this paper, we will present a method for quickly updating the solution to some l_1 norm minimization problems as new measurements are added. The result is an “l_1 filter” and can be implemented using standard techniques from numerical linear algebra. Our proposed scheme is homotopy based where we add new measurements in the system and instead of solving updated problem directly, we solve a series of simple (easy to solve) intermediate problems which lead to the desired solution.
The attendant presentation is here. Of related intested is Salman Asif's thesis we mentioned earlier entitled: Primal Dual Pursuit: A homotopy based algorithm for the Dantzig selector. One can also read the presentation slides, errata listand attendant Matlab files.
For those of you who know what an SBIR is, here is a DARPA one (from here):
SB091-010 TITLE: Panoramic Helmet-Mounted Display and Processing
TECHNOLOGY AREAS: Sensors, Electronics
OBJECTIVE: Develop a prototype of a panoramic, wide field of view helmet-mounted display, which presents the user with information from a minimum 90 degree horizontal field of view (FOV) with a goal of 120 degree horizontal and 40 to 50 degree vertical field of view, including signal processing adaptable to scene content.
DESCRIPTION: Significant advances have taken place in the development of large format imaging sensors, with mega-pixel sensors available in several spectral bands. These large sensors, which cover a wide field of view, fulfill the requirements for many applications, but are especially important in helmet-mounted systems for both ground and pilotage applications. However, the display technology essential to presenting the large amount of information generated by the sensor lags considerably behind the sensor technology. Currently, display technology is limited in field of view, and does not have the integral signal processing to match the capability of large format sensors and to adapt the information to meet user needs.
The need to efficiently display a large amount of information to the user is crucial to mission success. Information must be available to detect threats at the periphery of vision, to discern details as needed by the situation, and to perform intricate tasks. Meeting all of these requirements simultaneously requires a significant leap-forward in display and signal processing technology. The display must meld the requirement for full panoramic field of view with the need for an adaptable, high resolution instantaneous field of view.
The display must provide high image quality in a light weight package, with the ergonomics required for user acceptance, such as the center of mass optimized for head-mounted applications. The display format must be extended beyond the current state of the art, leading to innovative concepts in Mega-pixel displays with a high visual acuity in the central region and lower resolution in the periphery of the display. Novel signal processing and image reconstruction techniques must be applied to present the user with the essential scene content. The goal is to develop innovative sampling techniques that require only a small percentage of the data to reconstruct high quality scene information. These techniques have been demonstrated in radar and acoustic signal processing, but not implemented in helmet mounted displays. Although signal processing techniques have been demonstrated, there is considerable risk in the implementation of these techniques in display systems. However, the pay-off is large, enabling the user to grasp the large amount of information generated in a panoramic scene.
Emerging technologies in compressive sampling, where the information rate may be much smaller than the bandwidth, enables the presentation of only the essential information without loss of scene content. These new techniques can be integrated with wide field of view display components to present information from a wide field of view at minimum power, essential to helmet-mounted systems. The integrated display/processor not only presents information to the user, but also integrates functions to reduce workload, increase the situational awareness and enhance the ability to perform essential tasks.
In military display applications, a wide field of view combined with the flexibility to perform multiple functions, and elimination of display artifacts that detract from image quality, are essential to user acceptance of the technology. The display technology must have a fast response time so that the image is free of artifacts due to target movement or head-movement. Frame update rate of at least 60 Hz minimizes image artifacts and blurring. An innovative feature of the display technology should be the flexibility to integrate inputs from external sources as well as the ability to export selected areas to other sensor systems.
The physical configuration of the display must conform to the user with an unobtrusive format, conformal with the helmet, fitting similar to a visor, and with the display configured with optimum binocular overlap to provide high resolution and a contiguous view of displayed information. The brightness should be sufficient to present high contrast information, even in high light ambient environments. Also, the physical configuration must be such that illumination from the display is visible only to the user and keeps the system convert.
Applications include aviation and ground applications. The signal processing functions should be adaptable, allowing the display processing system to be used in multiple environments.
PHASE I: Define issues associated with the development of a novel concept in wide field of view display technology for helmet mounted applications; design the micro-system concept for panoramic helmet mounted display that includes adaptable compressive sampling to present essential scene content to the user. Perform simulations to demonstrate significant features of the display and advantages in military ground and airborne applications. Plans for Phase II will be proposed, including display component requirements and signal processing design.
PHASE II: Demonstrate the wide field of view display concept demonstrator with panoramic field of view, showing central region visual acuity approaching 20/20, with a minimum of 8 bits per pixel with a goal of 16 bits per pixel; show viability of the signal processing approach, display component technology, and the integration of signal processing with the display.
PHASE III: DUAL USE APPLICATIONS: Multiple applications for wide field of view display technology are in aircraft simulators and training systems. The display will present information from a wide field of view and provide a realistic view of the scene, while the integral signal processing will maintain and enhance the details in the scene necessary to perform intricate tasks.
REFERENCES:
1. Patterson R., Pierce B.J., Winterbottom M. C., “Perceptual Issues in the use of Head-Mounted Visual Displays” Journal of the Human Factors and Ergonomics Society, Vol 48 No. 3, 2006. pp 555-573.
2. Brickner M.S., “Helicopter Flights with Night-Vision Goggles-Human Factors Aspect” NASA Technical Memorandum 101039, March 1989.
3. E. J. Candès and M. Wakin. An introduction to compressive sampling. IEEE Signal Processing Magazine, March 2008 21-30. (pdf)
4. E. J. Candès. Compressive sampling. Proceedings of the International Congress of Mathematicians, Madrid, Spain, 2006. (pdf)
5. Compressive Optical MONTAGE Photography David J. Bradya, Michael Feldmanb, Nikos Pitsianisa, J. P. Guoa, Andrew Portnoya, Michael Fiddyc aFitzpatrick Center, Box 90291, Pratt School of Engineering, Duke University, Durham, NC 27708.
Digital Optics Corporation, 9815 David Taylor Drive, Charlotte, NC 28262.
Center for Optoelectronics and Optical Communications, University of North Carolina Charlotte, 9201 University City Blvd. Charlotte, NC 28223.
Proc. of SPIE Vol. 5907 590708-7.
KEYWORDS: Helmet-mounted displays; wide field of view; visual perception.
TPOC: Dr. Stuart Horn
Phone: (571) 218-4271
Fax: (703) 741-0086
E-mail: Stuart.Horn@darpa.mil
Photo: Igor Carron, Greenland from 30000 feet.
We consider compressed sensing of block-sparse signals, i.e., sparse signals that have nonzero coefficients occuring in clusters. Based on an uncertainty relation for block-sparse signals, we define a block-coherence measure and we show that a block-version of the orthogonal matching pursuit algorithm recovers block k-sparse signals in no more than k steps if the block-coherence is sufficiently small. The same condition on block-sparsity is shown to guarantee successful recovery through a mixed l2/l1 optimization approach. The significance of the results lies in the fact that making explicit use of block-sparsity can yield better reconstruction properties than treating the signal as being sparse in the conventional sense thereby ignoring the additional structure in the problem.
5. The Tiling Phenomenon of 1-bit Feedback Analog-to-Digital ConvertersTruong-Thao Nguyen, City University of New YorkTuesday, December 2, 4:10-5:00, SC 13126. Compressive Signal Processing using Manifold ModelsMike Wakin, Colorado School of MinesTuesday, December 9, 4:10-5:00, SC 1312.
His sparse recovery experiments wiki was mentioned earlier. Many items are of this presentation are detailed in Combining Geometry And Combinatorics: A Unified Approach to Sparse Signal Recovery by Radu Berinde, Anna Gilbert, Piotr Indyk, Howard Karloff and Martin Straus.
Traditional Nyquist-Shannon sampling dictates that a continuous time signal be sampled at twice its bandwidth to achieve perfect recovery. However, It has been recently demonstrated that by exploiting the structure of the signal, it is possible to sample a signal below the Nyquist rate and achieve perfect reconstruction using a random projection, sparse representation and an l_1-norm minimisation. These methods constitute a new and emerging theory known as Compressive Sampling (or Compressed sensing). Here, we apply Compressive Sampling to non-negative signals, and propose an algorithm—Non-negative Underdetermined Iteratively Reweighted Least Squares (NUIRLS) —for signal recovery. NUIRLS is derived within the framework of Non-negative Matrix Factorisation (NMF) and utilises Iteratively Reweighted Least Squares as its objective, recovering non-negative minimum l_p-norm solutions, 0 p 1. We demonstrate that—for sufficiently sparse non-negative signals—the signals recovered by NUIRLS and NMF are essentially the same, which suggests that a non-negativity constraint is enough to recover sufficiently sparse signals.
...I have placed the code for NUIRLS on my website at:
I can't wait to see the paper [1]. I then replied asking him:The main aim of my MLSP08 paper is to demonstrate that sparse norms are not always necessary for the special case where CS is entirely non-negative. Furthermore, in December I will present a paper [1] at a workshop in England where NMF is performed in the CS domain---recovering sparse coefficients AND a sparse basis from a compressively sampled matrix.
Is it your experience that NUIRLS is fast ?
My experience with standard NMF is that it is fast, further extensions such as adding sparseness constraints to convolutive models make it slow, when you include reweighting into the objective---as is the case for NUIRLS---it becomes very very slow. The graphs in the MLSP paper took a number of weeks. luckily though, we can use standard NMF updates if the signal is sufficiently sparse.
A quick comment: Anna's table actually contains *all* best known (to us) bounds for sparse recovery that work for arbitrary signals. I.e., it is not limited to schemes based on RIP-1 principle, but it also contains schemes based on usual RIP and Euclidean width properties. You can tell that by the last column (RIP-1 property leads to approximation bounds in the l1 norm, while other properties yield mixed norm or l2 norm bounds).
The license allows for it, so I've posted a copy of v0.4b on my site:
The license allows for redistribution non-commercially, as you can see in the file's includedReadme.txt. If you have a newer version or his site comes back up, please let me know.
Compressive-Sensing WorkshopFebruary 25 & 26, 2009Location: Duke UniversitySponsored by the AFRL ATR CenterCo-sponsored by AFOSR, ARO, DARPA, NGA and ONRThis workshop will bring together leading experts in the new field of compressive sensing (CS). The meeting will focus on new theory, algorithms and applications of CS. The format of the meeting will include formal talks, panel discussions and group interaction, as well as poster sessions. In addition to having talks from many of the leading CS researchers from academia, there will be talks from the members of the US government and industry, on directions for this new technology, including future research directions and programs.The meeting is jointly organized by Lawrence Carin (Duke) and Gregory Arnold (AFRL), who are affiliated with the AFRL ATR Center in Dayton, Ohio.The local Duke hosts for the workshop are Lawrence Carin, David Brady, Mauro Maggioni, Xiaobai Sun, and Rebecca Willet.The following members of the academic community have accepted invitations to present talks:
- Rich Baraniuk, Rice
- Thomas Blumensath, University of Edinburgh (England)
- Rob Calderbank, Princeton
- Ronald Coifman, Yale
- Ronald Devore, U South Carolina
- Yonina Eldar, Technion (Israel)
- Donald Goldfarb, Columbia
- Mario Figueiredo, Instituto Superior Tecnico (Portugal)
- Kevin Kelly, Rice
- Jian Li, U Florida
- James McClellan, Georgia Tech
- Kevin Murphy, UBC (Canada)
- Mark Neifeld, U Arizona
- Rob Nowak, U Wisconsin
- Stanley Osher, UCLA
- George Papanicolaou, Stanford
- Lee Potter, Ohio State
- Justin Romberg, Georgia Tech
- Guillermo Sapiro, U Minnesota
- Matthias Seeger, Max Planck Institute for Informatics (Germany)
- Joel Tropp, Caltech
- Martin Wainwright, UC Berkeley
- David Wipf, UC San Francisco
There will also be talks from members of the US government, including DARPA and NGA, as well as talks from members of industry.Participation: The meeting is open to all who wish to participate. If interested in being considered for a contributed talk or poster, please contact Lawrence Carin, at lcarin@ece.duke.eduStudent presentations: There will be a session dedicated to talks by graduate students. The presentation deemed to be of highest technical content, and presented best, will receive a $500 prize. Please contact Lawrence Carin at lcarin@ece.duke.edu if you would like to participate in the grad-student session.Schedule: The detailed agenda is being finalized, and will be posted soon. Talks will start at 8am on February 25, and end on February 26 at 5pm. The hotel room block is for the evenings of February 24 and 25, and the hotel is offering a special rate for February 26 for those who wish to stay an additional night.Registration: There will be a $250 registration fee, which covers all meeting participation, as well as breakfast and lunch on Feb. 25 and 26, and dinner on Feb. 25. The registration fee will be collected at the meeting. For members of the AFRL ATR Center as well as graduate students with valid student ID, the registration fee will be half-priced.Location and housing: The meeting will be held at the Washington Duke Inn and Golf Club. Room reservations may be made by calling 800-443-3853; when making reservations, mention the group name "AFRL" to get the special rates that have been negotiated. For government personnel, the government per-diem rate of $95/night will be honored; for non-government guests the rate is $125/night. To get these rates, reservations must be completed by February 6, 2009. We have negotiated a very special rate for this meeting, so please make reservations by this date; nightly rates are much higher after that date.Banquet: A dinner will be held on February 25, with this included in the registration fee. There will be a performance by The Pitchforks.Travel: The Raleigh-Durham airport (RDU) is a short distance from Duke University. It is recommended that guests take a cab ride from the airport, as there will be no need for transportation on the Duke campus
Une problématique liée à la fusion et la représentation de grand volume de données ainsi qu’à la possibilité d’acquérir des données de plus en plus résolues, doivent conduire à repenser la problématique de l’échantillonnage ainsi que celle de la compression. De nouvelles voies, à l’image des techniques de compressed sensing doivent être proposées et développées.
We recently proposed Counter Braids, an SRAM-only counter architecture for high-speed per-flow counting. Accurate per-flow counting was deemed complex and expensive because of the need for large arrays of counters operating at very high link speed (e.g. 40 Gbps). A naive algorithm needs an infeasible amount of SRAM to store both the counters and a flow-to-counter association rule, so that arriving packets can update corresponding counters at link speed. Counter Braids avoids the storage of flow-to-counter association by using random graphs generated on-the fly with hash functions. The counts of all flows remain compressed in SRAM at all times and incoming packets update directly the compressed counts, that is, no decompressing is necessary for updates. The compressed counts are transferred to software at the end of a measurement epoch and almost all flows are recovered exactly with a message passing decoding algorithm. One significant advantage of Counter Braids is the ease of implementation in hardware and the simplicity of updates. By prototyping Counter Braids on a NetFPGA board, we prove these claims in this paper. This particular implementation of Counter Braids achieves a 30-fold reduction in space compared to a naive hash-table based implementation.It looks we may just have to wait for three years before we have those on our desk as new FPGAs are coming out with some new technology developement promising to make them cheaper (Memristors Make Chips Cheaper).
In this talk, I will discuss constrained $\ell_1$ minimization methods in a unified framework for the recovery of high dimensional sparse signals in three settings: noiseless, bounded error and Gaussian noise. I will describe some improvements to the existing results in the literature by weakening the RIP conditions and tightening the error bounds. The improvement on the conditions shows that signals with larger support can be recovered accurately. I will also discuss connections between restricted isometry property and the mutual incoherence property, and present some extensions to the results of Candes, Romberg and Tao, and Donoho, Elad, and Temlyakov.Joint work with Tony Cai and Jun Zhang
AbstractIn many engineering applications, notions such as order or dimension of a model can be expressed as the rank of an appropriate matrix. To choose simple models, we seek low-rank matrices. The matrix rank minimization problem arises in linear system identification, statistical modeling of random processes, and data dimensionality reduction.The rank minimization problem is known to be computationally intractable.This talk discusses a convex relaxation based on semidefinite programming, and presents recent results in understanding under what conditions the relaxation is guaranteed to work. We discuss connections with the field of Compressed Sensing, which has demonstrated that sparse signals and images can be recovered from apparently incomplete sets of measurements. We ask what other objects or structures might also be recovered from incomplete, limited measurements, and present results on recovering matrices from partial information. Such problems are generally underdetermined, but when the matrix is known to be low rank or approximately low rank, the search for solutions becomes feasible. Applications arise in machine learning, system identification, and signal processing.
The linearly constrained matrix rank minimization problem is widely applicable in many fields such as control, signal processing and system identification. The linearly constrained nuclear norm minimization is a convex relaxation of this problem. Although it can be cast as a semidefinite programming problem, the nuclear norm minimization problem is expensive to solve when the matrices are large. In this paper, we propose fixed point and Bregman iterative algorithms for solving the nuclear norm minimization problem and prove convergence of the first of these algorithms. By using a homotopy approach together with an approximate singular value decomposition procedure, we get a very fast, robust and powerful algorithm that can solve very large matrix rank minimization problems. Our numerical results on randomly generated and real matrix completion problems demonstrate that this algorithm is much faster and provides much better recoverability than semidefinite programming solvers such as SDPT3.
A Bayesian approach is adopted for linear regression, and a fast algorithm is given for updating posterior probabilities. Emphasis is given to the underdetermined and sparse case, i.e., fewer observations than regression coefficients and the belief that only a few regression coefficients are non-zero. The fast update allows for a low-complexity method of reporting a set of models with high posterior probability and their exact posterior odds. As a byproduct, this Bayesian model averaged approach yields the minimum mean squared error estimate of unknown coefficients. Algorithm complexity is linear in the number of unknown coefficients, the number of observations and the number of nonzero coefficients. For the case in which hyperparameters are unknown, a maximum likelihood estimate is found by a generalized expectation maximization algorithm.
An ideal image segmentation algorithm could be applied to the segmentation of objects (e.g., tissue classes) without any adjustment for image acquisition device or application. However, a general-purpose, multiway segmentation of objects in an image/volume remains a challenging problem. In this talk, I will describe a recently developed approach to this problem this has been successful in several Siemens products. This segmentation approach inputs a few labeled points from a user (e.g., from mouse clicks) and produces a segmentation by computing the probabilities that a random walker leaving unlabeled pixels/voxels will first strike the labeled set. These probabilities may be computed analytically and deterministically by noting the exact mathematical equivalence with a combinatorial Laplace equation. The solution of the combinatorial Laplace equation admits interpretation of the algorithm as a steady-state electrical circuit simulation or as a minimization of the Dirichlet energy. Going beyond the segmentation problem, we may employ this energy minimization interpretation to minimize the p-norm of the spatial gradient of any function over neighboring pixels. By setting p=0 (i.e., maximizing sparsity), I willshow how we can also apply this energy minimization algorithm to image reconstruction for compressed sensing. Although compressed sensing and image segmentation appear to be very different problems, the conclusion of this work is that a common energy minimization approach may used to produce very good results for both problems.
