On Uncertainty Quantification of Lithium-ion Batteries

Forget devising the exact location of atoms, people, computing unimaginable quantum mechanical probability distributions, what if compressive sensing enabled us to figure out how to extend the lifetime of our smartphone batteries ? This is what this uncertainty quantification study using compressive sensing tries to do.

Figure from this tweet.

On Uncertainty Quantification of Lithium-ion Batteries by Mohammad Hadigol, Kurt Maute, Alireza Doostan

In this work, a stochastic, physics-based model for Lithium-ion batteries (LIBs) is presented in order to study the effects of model uncertainties on the cell capacity, voltage, and concentrations. To this end, the proposed uncertainty quantification (UQ) approach, based on sparse polynomial chaos expansions, relies on a small number of battery simulations. Within this UQ framework, the identification of most important uncertainty sources is achieved by performing a global sensitivity analysis via computing the so-called Sobol' indices. Such information aids in designing more efficient and targeted quality control procedures, which consequently may result in reducing the LIB production cost. An LiC6/LiCoO2 cell with 19 uncertain parameters discharged at 0.25C, 1C and 4C rates is considered to study the performance and accuracy of the proposed UQ approach. The results suggest that, for the considered cell, the battery discharge rate is a key factor affecting not only the performance variability of the cell, but also the determination of most important random inputs.

      Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Compressed Sensing Petrov-Galerkin Approximations for Parametric PDEs

Responding to a question I had on Twitter about the following paper and its connection with uncertainty quantification, Jean-Luc responded with the following:

Dear Igor,

Sorry for the late reply regarding your comment on Twitter. I prefered to reply per email as I'm guessing I'm going to go over the character limitation :)

Our work is directly related to problems in uncertainty quantification. The reason why it's not really obvious in this small note is that we had a 5 page restriction (this is mandatory for SampTA 2015) and decided to focus on the sampling/approximation results.

Why does it relate to uncertainty quantification? Consider the case where the 'parameters' y are in fact outputs of a random field with a certain probability distribution (see http://www.math.tamu.edu/~rdevore/publications/139.pdf or any other publications from Cohen, Devore, Schwab for more details), then you can recast the problem from uncertainty quantification into a parametric approach (in a sense): take a PCA / KL decomposition of the random field, and you get a parametric representation. Hence, yes, our results do apply for uncertainty quantification, even though they are phrased from another point of view right now.

We have other manuscripts in preparation that should be done (at least in a preprint form) by late June - I'll let you know when this is the case, if you have any interest? I will try to write a bit more details regarding the relation to uncertainty quantification and the relevance of our work on this topic.

Let me know if you have any questions,

Best,
Jean-Luc

Jean-Luc also added:

...I forgot to mention, it might be interesting to link to the following papers:
Starting papers:
* Cohen, Devore, Schwab, Analytic regularity and polynomial approximation of parametric and stochastic elliptic PDEs: http://www.math.tamu.edu/~rdevore/publications/143.pdf
* Cohen, Devore, Schwab, Convergence rates of best N-term Galerkin approximations for a class of elliptic sPDEs: http://www.math.tamu.edu/~rdevore/publications/139.pdf
The previous two papers describe the general ideas and first results behind the compressibility of the polynomial chaos expansions of the solution map.


* Cohen, Chkifa, Schwab, Breaking the curse of dimensionality in sparse polynomial approximation of parametric PDEs: http://e-collection.library.ethz.ch/eserv/eth:47390/eth-47390-01.pdf


Compressed sensing Petrov-Galerkin:
* Doostan et al, A non-adaptive sparse approximation of pdes with stochastic inputs: http://ctr.stanford.edu/ResBriefs09/10_doostan.pdf (first numerical steps)
* Rauhut, Schwab, Compressive sensing Petrov-Galerkin approximation of high-dimensional parametric operator equations: http://www.mathc.rwth-aachen.de/~rauhut/files/csparampde.pdf (theoretical analysis)
* Bouchot et al, Compressed sensing Petrov-Galerkin approximations for Parametric PDEs (direct application from the previous paper)

There has been quite a bit of research lately also on L2 minimization and projections on polynomial spaces. But I guess it gets a little out of the scope here. I'll send you pointers if you're interested.

Cheers,
JL

Thanks Jean-Luc! without further ado, here is the paper: Compressed Sensing Petrov-Galerkin Approximations for Parametric PDEs by Jean-Luc Bouchot, Benjamin Bykowski, and Holger Rauhut, Christoph Schwab

We consider the computation of parametric solution families of high-dimensional stochastic and parametric PDEs. We review recent theoretical results on sparsity of polynomial chaos expansions of parametric solutions, and on compressed sensing based collocation methods for their efficient numerical computation.
With high probability, these randomized approximations realize best N-term approximation rates afforded by solution sparsity and are free from the curse of dimensionality, both in terms of accuracy and number of samples evaluations (i.e. PDE solves). Through various examples we illustrate the performance of Compressed Sensing Petrov-Galerkin (CSPG) approximations of parametric PDEs, for the computation of (functionals of) solutions of intregral and differential operators on high-dimensional parameter spaces. The CSPG approximations reduce the number of PDE solves, as compared to Monte-Carlo methods, while being likewise nonintrusive, and being “embarassingly parallel”, unlike dimension-adaptive collocation or Galerkin methods. 

 

      Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Compressive Sampling of Polynomial Chaos Expansions: Convergence Analysis and Sampling Strategies

The sensing matrices in Uncertainty Quantification are very structured and so it is sometimes difficult to use solvers relying on gaussian measurement matrices and one wonders if solvers different from L1 could be contemplated in light of the recent SwAMP thing. Anyway, today's paper investigate in a deep fashion this subject. Let us note the use of phase transition as a comparison tool, great !

Compressive Sampling of Polynomial Chaos Expansions: Convergence Analysis and Sampling Strategies by Jerrad Hampton, Alireza Doostan

Sampling orthogonal polynomial bases via Monte Carlo is of interest for uncertainty quantification of models with high-dimensional random inputs, using Polynomial Chaos (PC) expansions. It is known that bounding a probabilistic parameter, referred to as {\it coherence}, yields a bound on the number of samples necessary to identify coefficients in a sparse PC expansion via solution to an ℓ1-minimization problem. Utilizing asymptotic results for orthogonal polynomials, we bound the coherence parameter for polynomials of Hermite and Legendre type under the respective natural sampling distribution. In both polynomial bases we identify an importance sampling distribution which yields a bound with weaker dependence on the order of the approximation. For more general orthonormal bases, we propose the {\it coherence-optimal} sampling: a Markov Chain Monte Carlo sampling, which directly uses the basis functions under consideration to achieve a statistical optimality among all sampling schemes with identical support. We demonstrate these different sampling strategies numerically in both high-order and high-dimensional, manufactured PC expansions. In addition, the quality of each sampling method is compared in the identification of solutions to two differential equations, one with a high-dimensional random input and the other with a high-order PC expansion. In both cases the coherence-optimal sampling scheme leads to similar or considerably improved accuracy.

Relevant previous entry:

• Sunday Morning Insight: So what is missing in Compressive Imaging and Uncertainty Quantification ?
• Infinity Continues to Matter: Generalized sampling: stable reconstructions, inverse problems and compressed sensing over the continuum
• On the Convergence of Approximate Message Passing with Arbitrary Matrices
• The SwAMP Thing! Sparse Estimation with the Swept Approximated Message-Passing Algorithm -implementation -

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Sunday Morning Insight: So what is missing in Compressive Imaging and Uncertainty Quantification ?

Paul Graham in one of his essay recently mentioned the following when it came to finding start-up ideas.

"Once you're living in the future in some respect, the way to notice startup ideas is to look for things that seem to be missing. If you're really at the leading edge of a rapidly changing field, there will be things that are obviously missing. What won't be obvious is that they're startup ideas. So if you want to find startup ideas, don't merely turn on the filter "What's missing?" Also turn off every other filter, particularly "Could this be a big company?" There's plenty of time to apply that test later. But if you're thinking about that initially, it may not only filter out lots of good ideas, but also cause you to focus on bad ones."

If you read this blog, you are already on the edge of knowledge, in a rapidly moving field and to a certain extent you are already living in the future.

So what is missing ?

Compressive sensing is a way of gathering data efficiently while knowing full well that, what you generally acquire, follows a power law of some sorts. With that in mind, people pushed the idea of concentration of measure results farther to more complex objects like matrices and then will eventually cross over to tensors (especially if we can leverage the matrix approach featured in the QTT format)

In a way, compressive sensing is successful because the framework has a wide appeal beyond signal processing. Indeed, if you read again what the analysis operator approach does, it is nothing more than solving a differential equation subjected to some measurements. The co-sparsity parameter represents  sources and/or the inhomogeneous part of these partial differential equations that are themselves constrained in the loss function.

All is well but there are dark clouds.

The last time I mentioned Uncertainty Quantification in the blog, it was to say that while a Polynomial Chaos approach could follow the traditional compressive sensing framework, in all likelihood, given the Donoho-Tanner phase transition,  you probably had to go through the extra complexity of wavelet chaos in order to find a winner. If you have ever dealt with polynomial series expansions, you know that all kinds of problems come from the coefficient thresholding we expect in compressive sensing. Even if some coefficients expansions are small they still matter ... at least empirically. It's known as the Gibbs phenomenon. 

Similarly, if you are part of the compressive sensing group on LinkedIn, you have seen that seemingly small questions lead to not so favorable answers for compressive imaging. In this instance, you realize that the only way to reconstruct a very nice image through some of the most advanced compressive sensing reconstruction algorithm is to ... cheat. You first have to acquire an image, threshold its series expansion and then acquire the compressive measurements from that thresholded version. When you do that, you get indeed near perfect reconstructions but it doubtful there is a CS camera that can do that.

The underlying reason for this disillusion in both CS imaging and UQ is that while CS works fine for sparse signals, it is not all that great for unknowns that are merely compressible, i.e. not sparse. In short, if you hope to do well because the object of interest is only compressible in terms of some eigenfunctions expansion, you might make a mistake. In both UQ or images, what is missing is a result for compressible signals and it just looks like the one we have is just not good enough.

As Paul said earlier "What is missing ?"

I think two ideas could take us out of this slump.

One: Maybe our sampling scheme for the eigenfunction expansion is chosen too early and we ought to rethink it in light of the work on infinite-dimensional compressive sensing (see [1] [2]). 

Two: The second idea revolves around learning the right analysis operator in both imaging applications and UQ.

Unlike the traditional approach in compressive imaging that relied on an eigenfunction expansion (which eventually led us to this slump), the analysis approach on the other hand, goes for what is obvious. The zeros are on one side of the homogeneous equation fulfilled by the field of interest. They are not epsilons, just zeros, the stuff that makes something sparse.

In imaging applications, you traditionally acquire the eigenfunctions expansion of a 2D projection of the plenoptic function. The TV-norm, a special case of analysis operator, is successful because the PSF of most cameras is degenerate. What if the PSF were not degenerate, what sorts of analysis operator approach should be used ? 

In UQ, you try to estimate how changes in the coefficients of the transfer equation will affect the solution of said equation. The question being answered is: What are the coefficient phase space of interest that is consistent with the measurements ?

Both problematic eventually rejoin in their need to develop an analysis approach of the following sort:

min || L(f) - c || subject to Ax = b

Where L represents the discretization of field transport operator (with unknown coefficients in UQ), c the boundary conditions or sources, A represents the hardware sensing mechanism and b the measurements.

Thank you Leslie Smith for the fruitful discussion.

Reference:

[1] B. Adcock & A. C. Hansen & E. Herrholz & G. Teschke, "Generalized sampling, infinite-dimensional compressed sensing, and semi-random sampling for asymptotically incoherent dictionaries".

[2] B. Adcock & A. C. Hansen, "Generalized Sampling and Infinite Dimensional Compressed Sensing".
[3]  Michael Elad, K-SVD Dictionary-Learning for Analysis Sparse Models.
[4] Uncertainty Quantification and Chemical Model Reduction, Habib N. Najm
[5] Mini-tutorial On Uncertainty Quantification: Intrusive UQ Propagation Methods by Alireza Doostan (similar info can be found here in Compressive Sensing and UQ)

Join our Reddit Experiment, Join the CompressiveSensing subreddit and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Wavelet Chaos and Compressive Sensing

I realize that the title of this entry has many buzzwords, but the following is an attempt at evaluating through a rule of thumb if a compressive sensing approach to Polynomial Chaos expansion as used in Uncertainty Quantification is a good move... or not. Constructive criticism, as usual, is welcome. 

To do that, I followed the generic idea of Polynomial Chaos decomposition and compressive sensing as highlighted in the work of Alireza Doostan [1,2] or that of Lionel Mathelin and Kyle Gallivan [3]. To get some example running, I used the PCE_LEGENDRE code featuring Polynomial Chaos Expansion using Legendre Polynomials but I could have used Chebfun. In this case:

"...We wish to analyze a stochastic PDE of the form:
                                         -div A(X,Y) grad U(X,Y) = F(X) where

• U(X,Y) is an unknown scalar function,

• A(X,Y) is a given diffusion function,

• F(X) is a given right hand side function,

• X represents dependence on spatial variables,

• Y represents dependence on stochastic variables..."

The usage is pretty simple:

Usage:
where the input is:

• n, the number of factors in the probability space.

• p, the maximum degree of the basis functions for the probability space.

and the output is

• nxy, the order of the matrix BXY. NXY = NX * NY.

• bxy, the system matrix, stored in sparse format.

• fxy, the right hand side.

[ nxy, bxy, fxy ] = pce_legendre_linear_assemble ( n, p )

So then by providing a shape for A and f, one can modify pce_legendre_linear_assemble.m and run something like:

[nxy,bxy,fxy]=pce_legendre_linear_assemble(4,3);

then by evaluating the least squares inverse for a specific fxy, I get a vector that features the Polynomial Chaos expansion coefficients of interest to the problem. I sort them out and plot them on the figure shown below: By playing a bit, one note that the size of the matrix to be inverted indeed grows exponentially as function of n and p.

As a rule of thumb, it looks as though one would need about 2/3 of the coefficients to get a good representation. So in the context of compressive sensing, it means that an acceptable approximation is about 1/3 sparse. Since the matrix of this system of linear equations is square and becomes large, the idea of compressive sensing is to make it short and fat and still recover an acceptable solution. As a rule of thumb, we are not going to be specific on the structure of this matrix. Hence, the initial system of equation 

A x = y

with A an nxn matrix, will be transformed into

G A x = G y 

with G a random matrix of size m x n. The idea is to now solve for a fatter and shorter matrix (GA) with the knowledge that x is sparse. Since the new matrix has no specific form, the Donoho-Tanner (DT) phase transition applies. I added on top of the DT phase transition found here, the K/M =2/3 (the endpoint M/N is equivalent to K/N=2/3).

What do we read from this graph ? For the level of sparsity being sought (1/3), an l_1 recovery effort would require a smaller matrix of size 0.9N x N instead of N x N !

This is such a small improvement that it is probably not worth the effort of changing drastically the problematic. From that, one wonders when it would be a good move to attempt a compressive sensing approach? My guess is that instead of using polynomial chaos expansion, one should really investigate a wavelet chaos expansion ? The idea is that a wavelet chaos approximation is likely to be more efficient in case the stochastic functional is peaky.

Reference:

[1] Compressive Sensing and Uncertainty Quantification

[2] A non-adapted sparse approximation of PDEs with stochastic inputs by Alireza Doostan, Houman Owhadi.

[3] A compressed sensing approach for partial differential equations with random input data by Lionel Mathelin and Kyle Gallivan

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Compressive Sensing and Uncertainty Quantification

One of the main issue in engineering is the disconnect between experimentalists and people running codes all day long. The disconnect occurs at several levels but one that is the most painful is the inability to iterate fast enough between the results of some code and the results of some experiments. Part of the problem stems from the experiments sometimes costing millions of dollars, another issue is that there is little infrastructure built-in forward codes to estimate uncertainties based on uncertainties of the model. Some of this hardly being addressed in the engineering curriculum and this is why I would have to salute the effort made at Duke to remedy this though the SAMSI effort program on Uncertainty Quantification. It turns out there is a connection to Compressive Sensing as shown in the different presentations by Alireza Doostan ( we featured him before)

• Stochastic PDEs, Sparse Approximations, and Compressive Sampling 
• A Compressive Sampling Approach to Sparse Polynomial Chaos Expansions

So the bounds on Legendre Polynomials and Spherical Harmonics are not so abstract after all!

If you wonder what Polynomial chaos coefficients are, you may want to look into these tutorials and other presentations:

• Mini-tutorial On Uncertainty Quantification: Intrusive UQ Propagation Methods by Alireza Doostan
• Sensitivity analysis and polynomial chaos for differential equations by Dongbin Xiu ( The videos for this talk are here)
• Nonintrusive Polynomial Chaos and Stochastic Collocation Methods for Uncertainty Analysis and Design by Michael S. Eldred.
• Inverse Problem and Calibration tutorial lecture by Peter Kitanidis .

More information about the SAMSI program on Uncertainty Quantification:

• High Dimensional Approximation for Uncertainty Quantification - November 10, 2011
• SAMSI/Sandia Summer School on Uncertainty Quantification - June 20-24, 2011

I have duplicated some elements of this entry and more on the Robust Mathematical Modeling blog.

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.